Graphs:Simple Applications of DFS and BFS
Simple Applications of DFS and BFS
In the preceding section we discussed two basic but powerful and efficient techniques for systematically searching a graph such that every edge is traversed exactly once and every vertex is visited once. With proper modifications and embellishments these search techniques can be used to solve a variety of graph problems. Some of the simple ones are discussed in this section.
Cycle Detection: The existence of a back edge (i.e., a nontree edge) during a depth- first search indicates the existence of cycle. To test this condition we just add an else clause to the if num[w] = 0 statement in DFS-Visit(v) procedure in Figure 4.9.
That is, if num[w] /= 0, (v, w) is a back edge, which forms a cycle with tree edges in the path from w to v.
Spanning Tree: If the input graph G for the depth-first (or breadth-first) algorithm is connected, the set TreeEdges at the termination of the algorithm in Figure 4.9 (or in Figure 4.10, for breadth-first) produces a spanning tree of G.
Connected Components: If, on the other hand, the input graph G = (V, E) is dis- connected we can use depth-first search to identify each of its connected components by assigning a unique component number compnum[v] to every vertex belonging to one com- ponent. The pseudocode of such an algorithm is given below (Figure 4.12)
Depth-First Search on a Digraph
Searching a digraph is somewhat more involved because the direction of the edges is an additional feature that must be taken into account. In fact, a depth-first search on a digraph produces four kinds of edges (rather than just two types for undirected graphs):
(i) Tree edges—lead to an unvisited vertex (ii) Back edges—lead to an (visited) ancestor vertex in the tree (iii) Down-edges (also called forward edges) lead to a (visited) descendant vertex in the tree, and (iv) Cross edges, lead to a visited vertex, which is neither ancestor nor descendant in the tree [3, 15, 16, 18, 19].
The simplest use of the depth-first search technique on digraphs is to determine a labeling of the vertices of an acyclic digraph G = (V, E) with integers 1, 2,... , |V |, such that if there is a directed edge from vertex i to vertex j, then i < j; such a labeling is called topological sort of the vertices of G. For example, the vertices of the digraph in Figure 4.13(a) are topologically sorted but those of Figure 4.13(b) are not. Topological sorting can be viewed as the process of finding a linear order in which a given partial order can be embedded. It is not difficult to show that it is possible to topologically sort the vertices of a digraph if and only if it is acyclic. Topological sorting is useful in the analysis of activity networks where a large, complex project is represented as a digraph in which the vertices correspond to the goals in the project and the edges correspond to the activities. The topological sort gives an order in which the goals can be achieved [1, 9, 18].
Topological sorting begins by finding a vertex of G = (V, E) with no outgoing edge (such a vertex must exist if G is acyclic) and assigning this vertex the highest number—namely, |V |.
This vertex is then deleted from G, along with all its incoming edges. Since the remaining digraph is also acyclic, we can repeat the process and assign the next highest number, namely |V |− 1, to a vertex with no outgoing edges, and so on. To keep the algorithm O(|V | + |E|), we must avoid searching the modified digraph for a vertex with no outgoing edges.
We do so by performing a single depth-first search on the given acyclic digraph G. In addition to the usual array num, we will need another array, label, of size |V | for recording the topologically sorted vertex labels. That is, if there is an edge (u, v) in G, then label[u] < label[v].
The complete search and labeling procedure TOPSORT is given in Figure 4.14.
Use the acyclic digraph in Figure 4.13(a) with vertex set V = {a, b, c, d, e, f, g} as the input to the topological sort algorithm in Figure 4.14; and verify that the vertices get relabeled 1 to 7, as shown next to the original names—in a correct topological order.
Comments
Post a Comment