Which is the best (in time complexity) algorithm for finding a cycle in directed graph?

Also are there 开发者_如何学Cany randomized algorithms for that. I need to find a single cycle as fast as possible, not all cycles.

Which is the best (in time complexity) algorithm for finding a cycle in directed graph?

Tarjan's strongly connected components algorithm. The time complexity if O( | V | + | E | ).

I'm not aware that this is possible to do in the general case, but if you know certain properties of the graph (such as its "distance from cycle-freeness" as described in the paper below), there exist randomized algorithms that with high probability will find a cycle quickly. Specifically, see the first algorithm in section 3 of the linked paper, with the corresponding analysis explaining how to extract the cycle.

As for deterministic algorithms, Mr. Saurav's answer is correct. In the worst case, you'll at least have to scan the entire input in order to correctly determine whether or not there is a cycle, which already requires O(|V| + |E|) time.

[1] http://arxiv.org/abs/1007.4230

the fastest one would be just a depth first graph traversal. this is because you are not specifying any particular topology and so any other approach could face a bad worst case. Asymptotically O(|E|). what you do is you label each node by the unique time you enter it as you recurse further and as soon as you find a node that already has a time label, there is your cycle and you halt.