Testing for Cycles in a Directed Graph

The final application of graph traversal that we consider in this section is to test a directed graph for cycles. An easy way to do this is to attempt a topological-order traversal using the algorithm given in Section . This algorithm only visits all the vertices of a directed graph if that graph contains no cycles.

To see why this is so, consider the directed cyclic graph shown in Figure . The topological traversal algorithm begins by computing the in-degrees of the vertices. (The number shown below each vertex in Figure  is the in-degree of that vertex).

  
Figure: A Directed Cyclic Graph

At each step of the traversal, a vertex with in-degree of zero is visited. After a vertex is visited, the vertex and all the edges emanating from that vertex are removed from the graph. Notice that if we remove vertex a and edge (a,b) from , all the remaining vertices have in-degrees of one. The presence of the cycle prevents the topological-order traversal from completing.

Therefore, the a simple way to test whether a directed graph is cyclic is to attempt a topological traversal of its vertices. If all the vertices are not visited, the graph must be cyclic.

Program  gives the implementation of the IsCyclic member function of the Digraph class. This Boolean-valued accessor returns true if the graph is cyclic. The implementation simply makes use of a CountingVisitor to count the number of vertices visited during a TopologicalOrderTraversal of the graph.

  
Program: Digraph Class IsCyclic Member Function Definition

The worst-case running time of the IsCyclic routine is determined by the time taken by the TopologicalOrderTraversal. Since , the running time of IsCyclic is when adjacency matrices are used to represent the graph and when adjacency lists are used.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.