Chapter 6: Graphs and Trees
Section 6.1 Graphs and Their Representations
Computer Representation of Graphs
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.”Array Pointer
Example 1: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.
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 following Figure shows an unweighted directed graph.
