Re: [Boost-users] Detecting cycles

From: Markus Svilans (msvilans_at_[hidden])
Date: 2008-04-16 17:26:35

You could tag each vertex or edge with a "visited" flag. Set "visited" 
to false initially. Then use a traversal algorithm to traverse the 
graph, starting at any vertex or edge. When each vertex or edge gets 
visited, check the state of the "visited" flag. If true, then stop 
because there is a cycle, because there is more than one route to that 
vertex or edge. If it's false, set it to true, and move on to the next 
vertex or edge.

Regards,
Markus.

Chartier Nicolas wrote:
> I wonder if someone knows an easy way to detect cycles in a graph.
> Any suggestion welcome ;)
>
> NC
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>