Representing Graphs
From
(→Adjacency List) |
(→Representation) |
||
| Line 8: | Line 8: | ||
<br/><br/> | <br/><br/> | ||
=== Representation === | === Representation === | ||
| - | {|class="wikitable | + | {|class="wikitable" align="left" style="width:18em;" background="gray" |
|colspan="3"|The graph pictured on the right has this adjacency list representation: | |colspan="3"|The graph pictured on the right has this adjacency list representation: | ||
|- | |- | ||
Revision as of 18:30, 29 March 2009
Adjacency Matrix
Adjacency List
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.
Representation
| The graph pictured on the right has this adjacency list representation: | ||
| a | adjacent to | b,c |
| b | adjacent to | a,c |
| c | adjacent to | a,b |
If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node and the other denoting the destination node of the corresponding arc. Typically, adjacency lists are unordered.
In an adjacency list representation, we keep, for each vertex in the graph, all other vertices which it has an edge to (that vertex's "adjacency list"). For instance, the representation suggested by van Rossum, in which a hash table is used to associate each vertex with an array of adjacent vertices, can be seen as an instance of this type of representation, as can the representation in Cormen et al in which an array indexed by vertex numbers points to a singly-linked list of the neighbors of each vertex.
One difficulty with the adjacency list structure is that it has no obvious place to store data associated with the edges of a graph, such as the lengths or costs of the edges. To remedy this, some algorithms texts such as that of Goodrich and Tamassia advocate a more object oriented variant of the adjacency list structure, sometimes called an incidence list, which stores for each vertex a list of objects representing the edges incident to that vertex. To complete the structure, each edge must point back to the two vertices forming its endpoints. The extra edge objects in this version of the adjacency list cause it to use more memory than the version in which adjacent vertices are listed directly, but are a convenient location to store additional information about each edge.
