Analysis of Algorithms : An Active Learning Approach

6.2 DATA STRUCTURE METHODS FOR GRAPHS 149

■ 6.2.2 The Adjacency List

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

stored as a one-dimensional array of size N, with each location being a pointer

to a linked list. There will be one list for each node, and that list will have one

entry for each adjacent node. Figure 6.3 shows the adjacency lists for the graph

and digraph in Fig. 6.1.

For weighted graphs and digraphs, the adjacency list entries would have an

additional field to hold the weight for that edge.

6.2.3

1. Give the adjacency matrix for the graph in question 1 of Section 6.1.2.


2. Give the adjacency matrix for the digraph in question 2 of Section 6.1.2.


3. Give the adjacency matrix for the graph in question 3 of Section 6.1.2.


4. Give the adjacency matrix for the digraph in question 4 of Section 6.1.2.


5. Give the adjacency list for the graph in question 1 of Section 6.1.2.


6. Give the adjacency list for the digraph in question 2 of Section 6.1.2.


7. Give the adjacency list for the graph in question 3 of Section 6.1.2.


8. Give the adjacency list for the digraph in question 4 of Section 6.1.2.

2

1

1

2

3

1

2

3

4

5

3

3

2

5

4

4

5

2

1

2

3

2

1

2

3

4

5

3

5

4

■FIGURE 6.3A

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

■FIGURE 6.3B

The adjacency list for the graph in

Fig. 6.1(b)

■6.2.3 EXERCISES