Connected Components and Strongly Connected Components

Connected Components and Strongly Connected Components

In a directed graph if we can reach every vertex starting from any vertex then such components are called connected components.

But what are strongly connected components? Well, a strongly connected component is a subset of connected components. The only difference is that in connected components if we can reach any vertex from any vertex but in Strongly connected components we need to have a two-way connection system i.e. if A to B vertices are connected by an edge then B to A must also be present.

So does the above-mentioned statement contradict to the fact that it is a directed graph?

What the hell are you speaking?

Well not actually. Firstly a directed graph is definitely not an undirected graph but a subset of it. But most importantly the statement doesn't say that we need to have a direct path from A to B and B to A. There might be an intermediate vertex.

Let's have a look into this through an image

Take a thorough look into the above diagram and try to get the connected and strongly connected components.

Well I was just kidding. Let's just find them together.
The strongly connected components are
A. 1-2-3
B. 4
C. 5
But the connected components are not the same
Connected components are
A. 1-2-3-4-5
Do you agree?
Definitely, you do. If you get anything else. Try doing again.
But, why are the strongly connected components same as connected components
This is because, in the above diagram, the component 1-2-3 can reach any vertex (out of 1,2 and 3) starting from any vertex in the component.
But now if we try to add 4 to the above component and make 1-2-3-4 as a single component, it is observed that we cannot reach any vertex from any vertex like suppose if we start from 4, we cannot connect to 1 or 2 or 3. Hence it violates the laws of Strongly connected components. Hence it is a separate strongly connected component.
Similarly, if we connect 5 we cannot reach 1,2,3 or 4 from it hence it is a single and a separated component.

If you think you have got the point comfortably then go for the following questions. Else drop in our comment box, the part you are not comfortable with.

Q1. Is a single undirected edge be called a Strongly connected component?
Q2. Rahul's teacher asks him to apply DFS on a given graph of 7 vertices. Rahul on doing so came up with the following conclusion:
a) Each vertex has the same in-degree and out-degree sequence
b) Edge set is empty
Then find A and B where A is the number of components that are present in strongly connected set and B is the number of components present in the connected components.
Q3. Let G=(V, E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?

Q4. Is a cyclic graph have strongly connected components the same as connected components?

Answers
A1. Strongly connected components are found through DFS only since here in a single undirected edge we can reach any vertex from any vertex so definitely it is strongly connected.

A2. Since the number of vertices =7
As there are no edges.
Thus the number of strongly connected componets=number of vertices=7
Similarly, the number of connected componets=7
So, A=7 and B=7

A3. option B
The option is pretty clear though. If we reverse the directions of all arcs in a graph, the new graph has the same set of strongly connected components as the original graph.

A4. A cyclic graph is formed by connecting all the vertex to the closest components. Thus definitely connected components have only 1 component but we cannot reach any vertex from any other vertex only if directed. Thus, may not have 1 strongly connected component. But definitely can have the same number of components when undirected only. 


In case of any doubt please feel free to ask.