Page 276 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 13: Graphs

Table 13.1(a) shows the adjacency matrix for the graph given in Figure 13.1. Notes

Table 13.1: Adjacency Matrix for the Graph in Figure 13.1
Vertice 1 2 3 4 5
1 0 1 1 0 1
2 1 0 1 0 0
3 1 1 - 1 1
4 0 0 1 0 1
5 1 0 1 1 0

You may observe that the adjacency matrix for an undirected graph is symmetric, as the lower
and upper triangles are same. Also all the diagonal elements are zero., since we consider graphs
without any self loops. Let us find adjacency matrix for a digraph given in Figure 13.5.

Table 13.2: Adjacency Matrix for Digraph in Figure 13.5

Vertice 1 2 3 4 5 6 7
1 0 1 1 1 0 0 0
2 0 0 0 0 0 0 0
3 0 0 0 0 1 0 0
4 0 0 0 0 0 1 0
5 0 0 0 1 0 0 1
6 0 0 0 0 0 0 0
7 0 0 0 0 0 1 0

The total number of 1’s account for the number of edges in the digraph. The number of 1’s in each
row tells the outdegree of the corresponding vertex.

13.3.2 Adjacency List Representation

In this representation, we store a graph as a linked structure. We store all the vertices in a list
and then for each vertex, we have a linked list of its adjacent vertices. Let us see it through an
example. Consider the graph given in Figure 13.11.

Figure 13.11
v
1
v
4
v
6
v
3
v v
2 5
The adjacency list representation needs a list of all of its nodes, i.e.

v
1
v 2
v
3
v
4
v 5
And for each node a linked list of its adjacent nodes.

LOVELY PROFESSIONAL UNIVERSITY 271