Finding Cycle in A Graph Using DFS
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
Low Level Design: LowLevelDesign.io
-
Frontend Engineering: FrontendEngineering.io
জযāĻŧ শ্রী রাম
🕉
-
Concept of
Strongly Connected Components (SCC)
is very similar to that of Cycles. Please visit the chapter
Strongly Connected Components (SCC) as well,
after having a strong grasp on
Finding Cycles
and
Cycle Detection Using DFS
TO HAVE A VERY WELL-ROUNDED KNOWLEDGE. You would be amazed to see how many different kinds of solutions you are able to think of for
a given problem.
For any nodes đ and đ, the node đ and đ belong to the same cycle if and only if đ and đ are strongly connected.
While doing DFS graph traversal if we find a back-edge then we can be certain that the graph has at least one cycle.
There are two great ways of doing it:
-
Tracking Visiting status of Nodes:
Significance of Node State of Visiting and Visited:
VISITING: The current Node is being processed, i.e, DFS for this Node has started, but not yet finished, which means all descendants in the DFS tree of this vertex are not processed yet. Which also implies, this vertex is in the function call stack.
While doing DFS, if a Node whose state is Visiting is encountered, then the inbound edge to the Node with state Visiting is back edge and hence there is a cycle.
VISITED: The current Node and all of its descendants are processed.
Algorithm:
Using the above two states of Nodes, find the back-edge is easy.
At any point of time while doing the DFS graph traversal, if you encounter a back edge that would imply that there is a cycle. Why? Let's suppose while doing a DFS graph traversal we just visited Node A. So we will be processing Node A now. Now, what does processing Node A mean? Processing Node A mean visiting and processing all of the descendents of Node A. So, while processing Node A (whose status is now Visiting and not Visited) what would it mean if we get Node A as part of DFS traversal ? This would mean that some descendant of Node A is pointing to Node A, which mean a descendent of Node A has a back-edge to Node A. And, what does this form? This form a cycle. Exactly. So at any point of time while doing a DFS traversal from a Node if we happen to find a back-edge, i.e, a node with Visiting status that would clearly mean that there is a cycle in the DFS tree for that Node. And this applies to the DFS traversal for any Node in a graph.
Login to Access Content
-
Node Coloring:
This is a very common but powerful approach. This is very similar to the first approach but instead of using Visiting and Visited states for Node this approach uses three colors for the Nodes: WHITE, GRAY, BLACK.
Three colors denote the following:
WHITE : Current Node is not processed yet. Initially, all nodes are WHITE.
GRAY: Similar to Visiting state of a Node. GRAY denotes the current Node is being processed, i.e, DFS for this Node has started, but not yet finished, which means all descendants in the DFS tree of this vertex are not processed yet. Which also implies, this vertex is in the function call stack.
While doing DFS, if a Node whose state is GRAY is encountered, then the inbound edge to the Node with state Visiting is back edge and hence there is a cycle.
BLACK : Similar to Visited status of Node. BLACK indicates the current Node and all of its descendants are processed.
While writing code, we often denote WHITE as 0, GRAY as 1 and BLACK as 2.
Algorithm:
Similar to the first approach. If at any point of time during a DFS traversal of a graph we encounter a Node with color GRAY, that would imply that there is a cycle.
Let's try to learn this approach by solving a problem.
Problem Statement: Non-Cyclic Nodes
In a directed graph, we start at some node and walk along a directed edge of the graph. If we reach a node that is terminal, i.e, it has no outgoing directed edges, we stop.
We say the starting node is non-cyclic if and only if we must eventually walk to a terminal node from that starting node without encountering any cycle.
Return all the non-cyclic starting nodes as an array in sorted order. You can start from any node in a given graph
The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form of 2-D array graph[][]: graph[i] is an array of nodes j such that for each j: (i, j) is a directed edge of the graph.
Solution:
Login to Access Content
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
