496
Graphs and Trees
496
Graphs and Trees
1
2
3
4
5
3
2
1
4
2
1
4
1
4
2
2
3
(b)
(a)
4
3
5
2
4
1
1
3
2
2
1
Figure 6.29
In a programming language that does not support pointers, we can still achieve
the effect of an adjacency list by using a multicolumn array (or an array of records),
where one column contains the nodes and another column contains the array index
of the next node on the adjacency list—a “pseudopointer.” The disadvantage of this
approach is that the maximum amount of storage space that might be needed for an
n-node graph must be set aside for the array; once we start to fill the array, new space
cannot be dynamically created if we learn that there are still more adjacent nodes.
example 21
The array-pointer representation of the graph of Figure 6.29a is shown in
Figure 6.30. A null pointer is indicated by an array index of 0.
1
2
3
4
5
6
7
8
9
10
11
Node
Pointer
Weight
3
1
4
2
4
2
2
4
2
1
1
3
6
7
9
0
10
0
8
0
0
11
0
Figure 6.30
In this array, row 2, representing node 2, has a pointer to index 7. At index 7
of the array, we find node 1 with weight 4, representing the arc of weight 4 from
node 2 to node 1. The pointer to index 8 says that the adjacency list for node 2 has
more entries. At index 8, we learn that there is an arc from 2 to 4 of weight 2, and
that this completes the adjacency list for node 2.