Discrete Mathematics for Computer Science

398 CHAPTER 6 Graph Theory

cycle-that is, those vertices of outdegree zero. Q is the queue of vertices in NotlnCycle

waiting to be processed. Array entry NumExits[v] is initialized as the current maximum for

the number of ways a directed cycle can exit vertex v. Initially, this is just the outdegree of

a vertex.

INPUT: Directed graph D = (V, E)

OUTPUT: TRUE if D contains a directed cycle and

FALSE if it does not

Initialize NotInCycle and Q to contain the vertices

with outdegree 0 and NumExits[ 1 ..I V I] to the outdegrees of the vertices of D

while Q 0 0

Remove the vertex v at the head of Q

for each w E V such that (w, v) e E do

Remove (w, v) from E

NumExits[w] = NumExits[w] - 1

if (NumExits[w] = 0) then

NotlnCycle = NotlnCycle U {w}

Put w at the end of Q

if (NotInCycle = V) return FALSE

else return TRUE

Initially, there is no way to know which vertices, other than vertices of outdegree zero,

cannot be in a directed cycle. The vertices with outdegree zero give the algorithm a place

to start. As the algorithm proceeds, any vertex v that is identified as not being in a directed

cycle has the edges with it as the head identified as edges not belonging to a directed

cycle. For all vertices w that are the tail of an edge not in a directed cycle, NumExits[w] is

decremented by one. If NumExits[w] becomes zero for some vertex w through this process,

then the vertex must have all the edges with it as the head the recognized as not being in

a directed cycle. The set NotinCycle merely collects the vertices that are identified as not

belonging to any directed cycle. If at the end of the procedure every vertex in the directed

graph is in NotlnCycle, then the digraph does not contain a directed cycle. If not every

vertex is an element of NotinCycle when the procedure terminates, there is a directed cycle

in D contained in the induced subgraph < V - NotlnCycle >.

6.16.2 Correctness of Directed Cycle Detection

Let us argue that the algorithm terminates and produces the correct answer. If no vertex

has outdegree zero, then the directed graph has a directed cycle by Exercise 2 in Section