To find cycles in a undirected graph, we can use a modified form of our standard depth-first-search algorithm. The text "The Algorithm Design Manual" by Steven S. Skiena provided the DFS and cycle detection algorithm we will use here, though it has been re-coded from memory and is being applied to our standard graph class from the other examples.
Our DFS algorithm naturally forms a tree from the graph. As it finds each new node, it detects creates a "tree-edge", and assuming it never finds any cycles, that is all it will ever find. If, however, we find a node in our search tree which points back to a previous node that we have already discovered in our DFS, then we have found a "back-edge". A back edge connects a node we've already found higher up the tree to the current node, which we know was reachable from the node we already found. So, any back edge implies a cycle exists. We can print the cycle by back-tracking from the node that contains the back-edge using the parent relationship, just like we did to print the shortest path found by Dijkstra's algorithm.
Read full article from Cycle in Undirected Graph
No comments:
Post a Comment