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