494
Graphs and Trees
In a simple weighted graph, the entries in the adjacency matrix can indicate
the weight of an arc by the appropriate number rather than just indicating the
presence of an arc by the number 1.
Adjacency List
Many graphs, far from being complete graphs, have relatively few arcs. Such
graphs have sparse adjacency matrices; that is, the adjacency matrices contain
many zeros. Yet if the graph has n nodes, it still requires n
2
data items to represent
the adjacency matrix (or more than n
2
∙2 if a triangular matrix is used), even if
many of these items are zero. Any algorithm or procedure in which every arc in
the graph must be examined requires looking at all n
2
items in the matrix, since
there is no way of knowing which entries are nonzero without examining them. To
find all the nodes adjacent to a given node n i requires scanning the entire ith row
of the adjacency matrix, a total of n items.
A graph with relatively few arcs can be represented more efficiently by storing only the nonzero entries of the adjacency matrix. This representation consists
of a list for each node of all the nodes adjacent to it. Pointers are used to get us
from one item in the list to the next. Such an arrangement is called a linked list.
There is an array of n pointers, one for each node, to get each list started. This
adjacency list representation, although it requires extra storage for the pointers,
may still be more efficient than an adjacency matrix. To find all the nodes adjacent
to n i requires traversing the linked list for n i , which may have far fewer than the
n elements we had to examine in the adjacency matrix. However, there are tradeoffs; if we want to determine whether one particular node n j is adjacent to n i , we
may have to traverse all of n i ’s linked list, whereas in the adjacency matrix we
could access element i, j directly.
example 18
Consider the directed graph of Figure 6.26.
3
2
4
1
Figure 6.26
The adjacency matrix is
a = ≥
1 1 0 0
0 0 1 1
0 1 0 0
0 0 1 0
¥
Graphs and Trees
In a simple weighted graph, the entries in the adjacency matrix can indicate
the weight of an arc by the appropriate number rather than just indicating the
presence of an arc by the number 1.
Adjacency List
Many graphs, far from being complete graphs, have relatively few arcs. Such
graphs have sparse adjacency matrices; that is, the adjacency matrices contain
many zeros. Yet if the graph has n nodes, it still requires n
2
data items to represent
the adjacency matrix (or more than n
2
∙2 if a triangular matrix is used), even if
many of these items are zero. Any algorithm or procedure in which every arc in
the graph must be examined requires looking at all n
2
items in the matrix, since
there is no way of knowing which entries are nonzero without examining them. To
find all the nodes adjacent to a given node n i requires scanning the entire ith row
of the adjacency matrix, a total of n items.
A graph with relatively few arcs can be represented more efficiently by storing only the nonzero entries of the adjacency matrix. This representation consists
of a list for each node of all the nodes adjacent to it. Pointers are used to get us
from one item in the list to the next. Such an arrangement is called a linked list.
There is an array of n pointers, one for each node, to get each list started. This
adjacency list representation, although it requires extra storage for the pointers,
may still be more efficient than an adjacency matrix. To find all the nodes adjacent
to n i requires traversing the linked list for n i , which may have far fewer than the
n elements we had to examine in the adjacency matrix. However, there are tradeoffs; if we want to determine whether one particular node n j is adjacent to n i , we
may have to traverse all of n i ’s linked list, whereas in the adjacency matrix we
could access element i, j directly.
example 18
Consider the directed graph of Figure 6.26.
3
2
4
1
Figure 6.26
The adjacency matrix is
a = ≥
1 1 0 0
0 0 1 1
0 1 0 0
0 0 1 0
¥