7.2 Cycle

Detect Cycle (Undirected Graph)

Detect Cycle is an common use function. It can detect a graph which is tree structure or not. It will be use on building the Minimum Spanning Tree.

The idea of Detect Cycle is very simple in an undirected graph. Go through the graph by DFS and find that is any node visit more than one times.

Algorithm

 Mark the root node as current node Mark current node as visited For each neighbor node of the current node, If it is not visited before, mark this node as current node and repeat process from step 2 Else if the node is visited and it is not the parent of current node, report the Cycle exists. Report the Cycle not exists

Time Complexity
It will visited every node and edges once, so time complexity is O (| V | + | E |)

SpaceComplexity
It will need to go forward alll nodes in the worst case, so the space complexity is O (| V |)

Pseudo Code

 ```Function DFS (Graph, Node, Parent) Mark Node as visited For each neighbor n of N do If n is not visited then Mark n as visited DFS (Graph, n, Node) Else if n is not Parent Report cycle found ```

Detect Cycle (Directed Graph)

Algorithm

 Mark the root node as current node Mark the Start Time of current node For each neighbor node of the current node, If it is not visited before, mark this node as current node and repeat process from step 2 Else if the node is visited and it is not the parent of current node, report the Cycle exists. Mark the Finish Time of the current node

Time Complexity
It will visited every node and edges once, so time complexity is O (| V | + | E |)

SpaceComplexity
It will need to go forward alll nodes in the worst case, so the space complexity is O (| V |)

Pseudo Code

 ```Function DFS (Graph, Node, Parent) Mark Node as visited For each neighbor n of N do If n is not visited then Mark n as visited DFS (Graph, n, Node) Else if n is not Parent Report cycle found ```
 © The University of Hong Kong Algorithms Library - hkual@cs.hku.hk