Simple implementation for detecting cycles in a directed graph in C#

Question

I wonder if you could help me with a simple implementation for detecting cycles in a directed graph in C#.

I've read about the algorithms but I'd like to find something already implemented, very simple and short.

I don't care about the performance because the data size is limited.

Whoever voted to close should post a comment why. This seems a perfectly valid question — Kieren Johnstone, Jun 21 '11 at 11:56

score 3 · Answer 1 · answered Jun 21 '11 at 12:00

3

Check out QuickGraph - it has loads of the algorithms implemented and it's quite a nice library to use.

answered Jun 21 '11 at 12:00

Mike Goatly

It seams your codeplex link is gone, but a fork is on github https://github.com/FubarDevelopment/QuickGraph – NewDeveloper Jul 06 '22 at 14:25

score 3 · Answer 2 · answered Jun 21 '11 at 12:02

3

Run a DFS on G and check for backedges.

At every node you expand just check if it is already in the currrent path.

answered Jun 21 '11 at 12:02

Patrick

2 Answers2