Discrete Mathematics for Computer Science

Finding a Cycle in a Directed Graph 397

User 1 I Tape Drive

User 2 Disk Drive

User 3 0*-- Printer

allocated requested

Figure 6.57 Deadlock.

Theorem 1. A WAITFOR graph represents a deadlock state for a single unit resource

scheme if and only if the digraph contains a directed cycle.

Finding a Cycle in a Directed Graph

The theorem that characterizes a WAITFOR graph that represents deadlock states is useful,

because there is an algorithm for detecting a directed cycle in a directed graph. The algo-

rithm proceeds by first recognizing a vertex v with outdegree zero as a vertex that cannot

be contained in any directed cycle. Then, all the edges with v as head can be identified

as not being in a directed cycle through v and eliminated from further consideration. This

follows because each of these edges leads to v, from which no continuation is possible. It

then follows that the process can be repeated for the subgraph formed by deleting all the

edges with v as head and putting v in the set of vertices that cannot be in a directed cycle.

This process can be repeated until no vertex remains or every vertex remaining is contained

in a directed cycle. An example of using this procedure is shown in Figure 6.58.

1 2 1 2 1 2 1 2

(^4 3 4 3 4 3 4 3)
4 not 2 not 3 not no directed
included included included cycle
in a in a in a exists
directed directed directed
cycle cycle cycle
Figure 6.58 Cycle-free directed graph.
If all the vertices of the directed graph can be identified as not being in a directed
cycle, then no directed cycle was present in the original directed graph.

6.16.1 Directed Cycle Detection Algorithm

A number of data structures are assumed to be available to the algorithm. The algorithm
uses NotInCycle as the initial set of vertices known to be unable to lie in any directed