Algorithm to figure out cycles in a directed graph?

[stickshift]

I remember going over some crap like that in my discrete math class, but I since sold the book :|

I'm working on a conflict serialization problem for my database class, and although I see no cycles i'd rather have an algorithm used to prove my case. Is it something like "the number of outgoing arrows must equal the number of incoming arrows"...? That's what I notice from the examples I have in front of me, but i'm still not sure.....

 

[oog]

This probably isn't what you're looking for, but couldn't you walk the entire graph, and check for repeated visits?

 

[Ameesh]

have two node pointers one walking at some speed, and another walking at twice the speed of the first one. If there is a cycle you will see both pointers equal each other before you see all the nodes of the entire graph.

if you have access to alot of memory and a hashtable class, store each node you see in a hash as you walk the grpah and check to see in the hash if you have seen the node while you walk.