is nowhere to go, and b is assigned the number 7. There are no unvisited nodes
left in the graph, so the process stops. The numbering scheme is shown in Figure
7.17b.
Figure 7.17
In reverse order of the counting numbers, we get
7
6
5
4
3
2
1
b
a
c
d
e
g
f
which is a topological ordering.
Now consider a graph G (undirected) that may not be a connected graph. A
connected component of G is a subgraph of G that is both connected and not a
subgraph of a larger connected subgraph. In Figure 7.19 there are three connected
components. Of course, if the original graph is connected, then it has only one
connected component.
Figure 7.19
praCtiCe 17 Use the depth-first search algorithm to do a topological sort on the graph in Figure 7.18.
Indicate the counting numbers on the graph.
Figure 7.18
Section 7.4 Traversal Algorithms
603
■