An introduction to graphs

First, let us understand what graphs are and the key terms related to graphs.

What is a graph?

A graph is a data structure that is represented as a set of nodes connected by a set of edges. Mathematically, we specify a graph G as (V, E), where V represents the nodes or vertices and E represents the edges between them, as shown in Figure 8.1:

Figure 8.1 – A simple graph

In the previous graph, we have the following:

V = {1, 2, 3, 4, 5, 6}

E = {(1,3), (2,3), (2,5), (3,6), (4,6), (5.6)}

Note that the order in which the nodes and edges are mentioned does not matter. The graph shown in Figure 8.1 is an undirected graph, which means that the direction of the edges does not matter. There can also be directed graphs in which the definition of the edge has some meaning, which gives importance to the direction of the edge. For example, a graph depicting the water flow of from various cities would have directed edges...