604
Graph Algorithms
A depth-first or breadth-first search can be used to find the connected components of a graph. We pick an arbitrary node as a source node and then conduct
a search. When the algorithm terminates, all visited nodes belong to one component. We then find an unvisited node in the graph to serve as a source for another
search, which will produce a second component. We continue this process until
there are no unvisited nodes in the graph.
Although we defined reachability only for directed graphs, the concept also
makes sense for undirected, unconnected graphs. Let us consider only simple undirected, unconnected graphs but impose the convention that, even though there
are no loops, each node is reachable from itself. Reachability then becomes an
equivalence relation on the set of nodes of the graph; our convention imposes the
reflexive property, and symmetry and transitivity follow because the graph is undirected. This equivalence relation partitions the nodes of the graph into equivalence classes, and each class consists of the nodes in one connected component
of the graph. Warshall’s algorithm can be applied to undirected graphs as well as
directed graphs. Using Warshall’s algorithm results in a matrix from which the
nodes making up various components of the graph can be determined, but this
requires more work than using the depth-first search.
As a final remark about depth-first search, we saw in Section 1.5 that the
programming language Prolog, when processing a query based on a recursive
definition, pursues a depth-first search strategy (Example 40).
S e c t i o n 7 . 4 revieW
tecHniQueS
• Conduct a depth-first search of a graph.
• Conduct a breadth-first search of a graph.
main iDeaS
• Algorithms exist to visit the nodes of a graph
systematically.
• Depth-first and breadth-first searches can serve as a
basis for other tasks.
W
W
exeRciSeS 7.4
For Exercises 1–6, write the nodes in a depth-first search of the following graph, beginning with the node specified.
1. a
2. c
3. d
4. g
5. e
6. h
Graph Algorithms
A depth-first or breadth-first search can be used to find the connected components of a graph. We pick an arbitrary node as a source node and then conduct
a search. When the algorithm terminates, all visited nodes belong to one component. We then find an unvisited node in the graph to serve as a source for another
search, which will produce a second component. We continue this process until
there are no unvisited nodes in the graph.
Although we defined reachability only for directed graphs, the concept also
makes sense for undirected, unconnected graphs. Let us consider only simple undirected, unconnected graphs but impose the convention that, even though there
are no loops, each node is reachable from itself. Reachability then becomes an
equivalence relation on the set of nodes of the graph; our convention imposes the
reflexive property, and symmetry and transitivity follow because the graph is undirected. This equivalence relation partitions the nodes of the graph into equivalence classes, and each class consists of the nodes in one connected component
of the graph. Warshall’s algorithm can be applied to undirected graphs as well as
directed graphs. Using Warshall’s algorithm results in a matrix from which the
nodes making up various components of the graph can be determined, but this
requires more work than using the depth-first search.
As a final remark about depth-first search, we saw in Section 1.5 that the
programming language Prolog, when processing a query based on a recursive
definition, pursues a depth-first search strategy (Example 40).
S e c t i o n 7 . 4 revieW
tecHniQueS
• Conduct a depth-first search of a graph.
• Conduct a breadth-first search of a graph.
main iDeaS
• Algorithms exist to visit the nodes of a graph
systematically.
• Depth-first and breadth-first searches can serve as a
basis for other tasks.
W
W
exeRciSeS 7.4
For Exercises 1–6, write the nodes in a depth-first search of the following graph, beginning with the node specified.
1. a
2. c
3. d
4. g
5. e
6. h