Section 6.1 Graphs and Their Representations
495
example 19
The adjacency list for the graph of Figure 6.25 contains a four-element array of
pointers, one for each node. The pointer for each node points to an adjacent node,
which points to another adjacent node, and so forth. The adjacency list structure is
shown in Figure 6.27.
1
1
2
1
1
2
3
4
2
3
4
3
4
4
3
Figure 6.27
In the figure the dot indicates a null pointer, meaning that there is nothing more to be
pointed to or that the end of the list has been reached. We have dealt with parallel arcs
by listing a given node more than once on the adjacency list for n i if there is more than
one arc between n i and that node. Note that the arrow in list 1 from the 2 node to the 4
node does not mean that there is an arc from node 2 to node 4; all the elements in the
node 1 list are adjacent to node 1, not necessarily to each other.
praCTiCe 17 Draw the adjacency list representation for the graph shown in Figure 6.28.
2
4
3
1
Figure 6.28
■
In an undirected graph, each arc is represented twice. If n j is on the adjacency
list of n i , then n i is also on the adjacency list of n j . The adjacency list representation
for a directed graph puts n j on the list for n i if there is an arc from n i to n j ; n i would
not necessarily be on the adjacency list for n j . For a labeled graph or a weighted
graph, additional data items can be stored with the node name in the adjacency list.
example 20
Figure 6.29a shows a weighted directed graph. The adjacency list representation
for this graph is shown in Figure 6.29b. For each record in the list, the first data
item is the node, the second is the weight of the arc to that node, and the third is the
pointer. Note that entry 4 in the array of startup pointers is null because there are
no arcs that begin at node 4.