Fidning a cycle in a directed graph.

**apacz** · 10-31-2005

Hi,
I have to find a cycle in a directed graph. I thought about such algorithm:
1) Create a queue Q.
2) Mark all vertexes as they are in a cycle.
2) Add to Q all vertexes which don't have an edge leading to another vertex (mark each vertex as it is not in a cycle).
3) While Q is not empty:
3.a) take a front element (let's say F) from Q.
3.b) for all F predecessors decrease the number of vertexes which F's predeccesor lead. If the numer is <= 0 add to Q and mark this vertex as it is not in a cycle.

Is it correct algorithm? For small examples it seems to be good but in some bigger graphs which I can't draw on paper it says that there is a cycle but for sure there is not.
Thanks,
apacz

**Rashakil Fol** · 10-31-2005

This looks like a correct algorithm (if there are finitely many nodes). Are you implementing it exactly as you've described it? It would be even more correct if you used the word 'vertices.' :-)

What you have written down is essentially the same algorithm as topological sort, which will visit every node if and only if there are no cycles. ('Topological sort' has an extra step, (3.c), that pushes F onto a list that gets returned.)

**apacz** · 10-31-2005

Thanks for reply. Yes, I implemented it as I've described and really I have no clue what's wrong there - I'm working on it since yesterday and can't find the bug or what it is.

**apacz** · 10-31-2005

Hm... Can I use this algorithm for directed multi graphs? Maybe becouse of that it doesn't work but from the logical point of view it should work ok.

--
I find an example for which this algorithm doesn't work properly.
We have a graph with 6 vertices and 6 edges:
A pari (a b) means that there is an edge from a to b (a->b):
2 2
1 2
3 4
4 2
4 2
2 6
So at the beggining we add to Q vertex number 6 (it doesn't lead to any other vertex) and 5 (it is separated from the rest of the graph).
We take a 6 from queue and check that 2 leads to 6. So we decrease the numer of vertices that 2 lead but it is still > 0. Queue is empty so we stop the algorithm.
And in a 'cycle' we have 1 2 3 4 but there should be only 2. (2->2 and 2<-2).

**Rashakil Fol** · 10-31-2005

The algorithm doesn't find cycles; it only finds if there exists a cycle.

If you want some particular cycle, you can use a modification of depth-first transversal.

**apacz** · 10-31-2005

Hi,
I want to find which vertices are in a cycle - it doesn't matter if in different cycle or in the same - I just want to know if each vertex is in a cycle. Can you recommend me any algorithm for that ? I need it done in O(n). Btw... What is exactly "depth-first transversal" ?
Regards.

**Rashakil Fol** · 10-31-2005

Exactly what information do you want returned by the algorithm? And what do you mean by 'n'?

**apacz** · 10-31-2005

I have a graph which consist n vertices and an array bool cycle[n] and I want algorithm to fill that array of cycle[x]=1 if and only if vertex is in a cycle.
Regards.

**Rashakil Fol** · 10-31-2005

Okay.

Step 1. Run the algorithm posted above.
Step 2. Reverse the direction of all the remaining edges in the graph (that don't point to or from marked nodes).
Step 3. Run the algorithm posted above with whatever nodes are left.

The remaining unmarked nodes are all part of some cycle.

Note that you really shouldn't implement the algorithm this way. IMO, your graph datastructure is best designed so that from a given node, you can immediately see incoming and outgoing edges and iterate through them in O(I+O) time, where I+O is the indegree and outdegree of that node. If this is the case, then there's no need for step 2 -- you can implement step three with a slightly different algorithm (possibly calling the same function or entering the same loop that performs step one, only with a different value for some boolean flag).

(If you actually perform step 2, reversing the direction of all remaining edges, the algorithm takes O(N+E) time, where E is the number of edges, and that can be as large as O(N^2). For some algorithms, this is unavoidable, and O(N+E) is considered linear time. But cycle finding can be done more quickly.)

**apacz** · 10-31-2005

Thank you very much for such comprehensive anwer. Now I got it all

.

Thread: Fidning a cycle in a directed graph.

Thread Tools

Search Thread

Display

Fidning a cycle in a directed graph.

Similar Threads

error help making no sense

How to use C++ graphs?

Help w/ graph as adjacency matrix

determining a path through the graph

Minimize crossing edges in undirected graph