|
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
|
|