Analysis of Algorithms : An Active Learning Approach

148 GRAPH ALGORITHMS

because it would not be very large, so even a sparse graph would not waste

many entries. In situations where the graph has many edges and begins to

approach a complete graph, an adjacency matrix would be best because there

would be few empty entries.

The following sections give the details on adjacency matrix and list methods.

■ 6.2.1 The Adjacency Matrix

An adjacency matrix, AdjMat, for a graph G = (V,E), with |V| = N, will be

stored as a two dimensional array of size NN. Each location [i,j] of this

array will store a 0, except if there is an edge from node vi to node vj, the loca-

tion will store a 1. More formally,

The adjacency matrices for the graph and digraph in Fig. 6.1 are given in

Fig. 6.2.

For weighted graphs and digraphs, the adjacency matrix entries would be ∞

if there is no edge and the weight for the edge in all other cases. The diagonal

elements would be 0, because there is no cost to travel from a node to itself.

AdjMat[]ij,^1 if vivj∈E

^0 if vivj∉E





= for all i and j in the range 1 to N

12345

101100

210110

311001

401001

500110

12345

101100

210000

301000

400101

501010

■FIGURE 6.2A

The adjacency matrix for the graph in Fig. 6.1(a)

■FIGURE 6.2B

The adjacency matrix for the digraph in Fig. 6.1(b)