Definitions
Applications: Representing a Graph in Computer Memory
Representing any graph, directed or undirected, in computer memory is
accomplished with the use of an array of linked lists or an adjacency
matrix.
Let the vertices of a graph be
.
The linked-list representation of
is given by an array
of linked lists, where
is a linked list of vertices
for which
is an edge of
.
Example
Figure 3:
Below is the linked-list representation of the above graph.
Figure 4:
|
The adjacency matrix
of
is the square matrix of order , where
if
is adjacent to
otherwise.
Example
| 0 | 1 | 2 | 3 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 3 | 1 | 0 | 0 | 0 | 1 | 4 | 0 | 1 | 0 | 1 | 0 |
This is the 5x5 adjacency matrix for the graph of the
previous example. The row and column indices (0 through 4) are
highlighted. The entry
also is highlighted
(for no reason other than to demonstrate the notation).
|