Graph: Depth First Search
Suppose, you are trying to build a project and it has multiple modules. Different modules may depend on each other for their functionality to work. For example, your project has namely, A, B, and C modules.
B depends on A
C depends on B
A depends on C
Here, we can see there is a cyclic dependency in the project which causes an issue.
A cyclic dependency in an IDE indicates that there is a cycle in the build paths between modules. Because of this cycle, the IDE does not know which module to compile first.
One such algorithm to check if a cyclic dependency exists in the project is by using the DFS of the modules. You can modify the generic DFS algorithm and make it work for your specific use case.
How DFS works?
Explore the current node. If the current node is A, then we will start exploring its depth. At node B, we have two choices, so we will explore the depth of both the choices one by one. If we select node C first then the sequence will be, A -> B -> C -> F -> E, else it will be A -> B -> E -> C -> F
Recursion Stack
If we recursively explore each node, then the stack trace will look like this:
Here, we are using a used array to keep track of the nodes that are already traversed so that we don’t traverse the same node again and can backtrack from there. One more observation here is that there are some nodes that are not connected, eg. node D. So, we need to call DFS for all the nodes in the graph, such that we don’t miss the unconnected components from our depth-first traversal.
Code Analysis
Complexity Analysis
Time Complexity: O(V+E) as we have to check all the vertices and the edges of the graph.
Space Complexity: It will use the function call stack and the maximum memory used will be equivalent to the longest depth possible from a node. In case of a skew graph (worst case), it will be O(E), where E is the total number of edges.
Guys I really hope that you find this article valuable! If still, you have any queries, you can surely discuss them in the comment section below.
Thanks a lot for devoting your time to this blog.
