Why Conventional DFS Method Cannot Be Used to Find the Strongly Connected Components?
When we talk about searching through graphs, the DepthFirst Search (DFS) method often comes up as a goto strategy. It's like going down a path as far as you can until you hit a dead end, and then backtracking to explore new paths. However, when it comes to identifying strongly connected components in a directed graph, the usual DFS method falls short. Let's explore why this is the case.
In a nutshell, DFS is great for exploring all the vertices & edges in a graph, but it doesn't account for the direction of those edges. This is fine for finding connected components in an undirected graph, where paths can go in any direction. But, for strongly connected components, where we need to find paths that go both ways between any two vertices, regular DFS doesn't cut it.
Here's the kicker: even if we run DFS from every vertex in a directed graph, we might end up marking all vertices as visited without actually verifying if every vertex is reachable from every other vertex in both directions. This is because DFS, in its conventional form, doesn't check for the reverse path, which is crucial for determining strongly connected components.
To effectively identify strongly connected components, we need an enhanced approach that considers the directionality of paths and ensures that for any two vertices in a component, there's a way to get from one to the other and back. This is where algorithms like Kosaraju's or Tarjan's come into play, which modify & extend the DFS approach to suit the specific needs of exploring strongly connected components.
Connecting Two Strongly Connected Components by a Unidirectional Edge
Linking two strongly connected components (SCCs) in a directed graph with a unidirectional edge creates an interesting scenario. Let's dive into this concept without any fluff.

Imagine you have two groups of vertices, let's call them Group A & Group B. Each group forms a strongly connected component, meaning you can travel from any vertex to any other vertex within the same group, following the direction of the edges.

Now, if we draw a unidirectional edge from a vertex in Group A to a vertex in Group B, we've created a connection between the two SCCs. However, this doesn't merge them into one big SCC. Why? Because for a set of vertices to be considered a strongly connected component, you must be able to reach every vertex from any other vertex and return back, respecting the direction of the edges.

By adding just a oneway street (our unidirectional edge) from Group A to Group B, we haven't provided a way to get back from Group B to Group A. This means, while there's a path from A to B, the lack of a return route keeps them as two separate SCCs.
This concept is crucial in understanding the structure of directed graphs and how components interact with each other. It highlights the importance of directionality in connections and the criteria that define strongly connected components.
Frequently Asked Questions
Can a single vertex be considered a Strongly Connected Component?
Yes, a single vertex can be considered a Strongly Connected Component (SCC) since it trivially satisfies the definition. There's a path (albeit, a trivial one) from the vertex back to itself.
How does adding an edge between two SCCs affect their strong connectivity?
Adding an edge from one SCC to another doesn't merge them into a single SCC. For two SCCs to combine, there must be a path from every vertex in one SCC to every vertex in the other, and vice versa, which a single edge doesn't achieve.
Why can't conventional DFS find Strongly Connected Components in a directed graph?
Conventional DFS doesn't account for the directionality required for SCCs. It can traverse a graph, but it doesn't ensure that there's a path in both directions between any two vertices, which is a must for strong connectivity.
Conclusion
In this article, we've explored the fascinating world of Strongly Connected Components (SCCs) within directed graphs. We started by understanding the difference between connected and strongly connected components, highlighting the importance of directionality in the latter. We then looked into why the conventional DepthFirst Search (DFS) method falls short when it comes to finding SCCs, emphasizing the need for algorithms that consider the bidirectional connectivity essential for SCCs.
You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.