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.