Graph Terminology in Data Structures: Explained with Examples

In this book, the following terms related to graphs are used:

Directed graph

A directed graph is a graph G = with the property that its edges have directions. An edge E: (vi, vj) means that there is an arrow whose head is pointing to vj and the tail to vi. A directed graph is shown in Figure 1 below. For example, (B, A), (A, D), (C, D), etc are directed edges. A directed graph is also called a diagraph.

Undirected graph

An undirected graph is a graph G = with the property that its edges have no directions, i.e., the edges are two ways as shown in Figure 2 below. For example, (B, A), (A, B), etc. are two way edges. A graph always refers to an undirected graph.

Weighted graph

A weighted graph is a graph G = with the property that its edges have a number or label associated with it. The number is called the weight of the edge. A weighted graph is shown in Figure 3 below. For example, (B, A) 10 may mean that the distance of B from A is 10m. A weighted graph can be an undirected graph or a directed graph.

Path

It is a sequence of nodes in which all the intermediate pair nodes between the first and the last nodes are joined by edges as shown in Figure 4 below. The path from A to F is shown with the help of dark edges. The path length is equal to the number of edges present in a path. The path length of A-D-E-F is 3 as it contains three edges.

However in the case of weighted graphs, the path length is computed as the sum of labels of the intermediate edges. For example, the path length of path A-D-C-E of Figure 3 above is (11 + 12 + 9), i.e., 32.

It may be noted that if no node occurs more E E than once in a path then the path is called a simple path. For example in Figure 2 above, A-B-C is a simple path. However, the path A-D-E-C-D is not a simple path.