1.
Introduction
2.
Difference between Connected & Strongly Connected Components?
3.
Why Conventional DFS Method Cannot Be Used to Find the Strongly Connected Components?
4.
Connecting Two Strongly Connected Components by a Unidirectional Edge
5.
5.1.
Can a single vertex be considered a Strongly Connected Component?
5.2.
How does adding an edge between two SCCs affect their strong connectivity?
5.3.
Why can't conventional DFS find Strongly Connected Components in a directed graph?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Strongly Connected Components

Pallavi singh
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

Graph theory is a fascinating area of mathematics and computer science that deals with networks of points connected by lines. It’s all about how these points, called vertices, are linked together. A key concept in this field is "strongly connected components." Simply put, a strongly connected component (SCC) in a directed graph is a section where every vertex is reachable from every other vertex in the same section.

This article will help you learn the differences between connected and strongly connected components, why we can't always use the conventional depth-first search (DFS) to find SCCs, and what happens when you connect two SCCs with a one-way path.

## Difference between Connected & Strongly Connected Components?

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Why Conventional DFS Method Cannot Be Used to Find the Strongly Connected Components?

When we talk about searching through graphs, the Depth-First Search (DFS) method often comes up as a go-to 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 one-way 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.

### 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 Depth-First 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 DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Live masterclass