Data Structures and Algorithms Using Python

In this chapter we will discuss another non-linear data structure: graph. We have already discussed a non-linear data structure, tree, where we found the hierarchical relation among nodes. Every parent node may have zero or more child nodes, i.e. the relationship is one-to-many. In graph, we will find that every node may be connected to any node, i.e. the relationship is many-to-many. Here we will discuss various terms related to a graph and then its representation in memory. We will also discuss the operations on a graph as well as its different applications.

12.1 Definition and Concept

A graph is a very important non-linear data structure in computer science. A graph is a non-linear data structure that basically consists of some vertices and edges. We can define a graph, G, as an ordered set of vertices and edges, i.e. G = {v, e}, where v represents the set of vertices, which is also called nodes, and e represents the edges, i.e. the connectors between the vertices. Figure 12.1 shows a graph where the vertex set v = {v1, v2, v3, v4, v5, v6} and the edge set e = {e1, e2, e3, e4, e5, e6, e7, e8, e9}, i.e. the graph has 6 vertices and 9 edges.

12.2 Terminology

In this section we will discuss the various terms related to graphs.

Directed graph: If the edges of a graph are associated with some directions, the graph is known as a directed graph or digraph. If the direction of an edge is from vi to vj, it means we can traverse the nodes from vi to vj but not from vj to vi. An edge may contain directions in both sides. Then we may traverse from vi to vj as well as from vj to vi. Figure 12.2 shows a directed graph.

Undirected graph: When there is no direction associated with an edge, the graph is known as undirected graph. In case of undirected graph, if there is an edge between the vertex vi and vj, the graph can be traversed in both directions, i.e. from vi to vj as well as from vj to vi. The graph shown in Figure 12.1 is an undirected graph.