1.
2.
Problem
3.
Solution
3.1.
Idea:
3.2.
Algorithm:
3.3.
Implementation in Java
4.
4.1.
What is a weakly connected component in a graph?
4.2.
What is a strongly connected component in a directed graph?
4.3.
What are weakly connected components?
4.4.
Can a graph be both weakly connected and strongly connected?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Weakly Connected Components in a Directed Graph

GAZAL ARORA
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

A weakly connected graph is a directed graph in which there exists a path between every pair of nodes, regardless of the direction of the edges. In other words, if the graph was undirected, it would be a connected graph. However, in a directed graph, connectivity is more complex as it depends on the direction of the edges, and a weakly connected graph can have nodes that are only reachable in one direction.

In a directed graph, weakly connected components are subsets of nodes where each node can be reached from any other node by following edges in any direction. Understanding weakly connected components is important in analyzing the structure of a graph and can have practical applications in various fields such as social network analysis and transportation planning. In this article, we will look in more detail about this topic.

## Problem

Given a directed graph G, find all the weakly connected components in G. A weakly connected component is a subgraph of a directed graph in which all vertices are connected by some path, irrespective of edge direction.

Input:

1. An integer n represents the number of vertices in the graph.
2. An integer k represents the size of the adjacency list.
3. An array G represents the adjacency list.

Output: Print all the weakly connected components of the given graph in separate lines.

Alert Ninjas:  Donâ€™t stop now! Enroll in the Competitive Programming course today. Learn the art of writing efficient code and compete in code competitions worldwide.

For Example,

Input: N = 7, k = 6, G = {{0,1}, {1,2}, {2,3}, {3,4}, {4,0}, {5,6}}.

In the above given directed graph G, letâ€™s draw its corresponding undirected graph whose edges are obtained by removing the arrowheads from the edges in G and making them bidirectional.

Both the components of the above-undirected Graph are connected; therefore, these two are weakly connected components of the input directed Graph.

Output: [0, 1, 2, 3, 4]

[5, 6]

Recommended: Try to solve it yourself before moving on to the solution.

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

## Solution

### Idea:

The idea is to use the fact that the WCC of a graph is the connected components of the undirected graph formed by removing the arrowheads from the edges in G and making them bidirectional.

### Algorithm:

1. Construct the corresponding undirected graph of the given directed graph.
2. Find all the connected components of the new undirected graph, and these will be the weakly connected components of the given directed graph.

### Implementation in Java

Input: N = 7, k = 6, G = {{0,1}, {1,2}, {2,3}, {3,4}, {4,0}, {5,6}}.

Output:

Time Complexity: O(V+E).
Check out this problem - No of Spanning Trees in a Graph

### What is a weakly connected component in a graph?

A weakly connected component (WCC) is a subgraph of a directed graph in which all vertices are connected by some path, regardless of edge direction. A weakly connected component in an undirected graph is also a strongly connected component.

### What is a strongly connected component in a directed graph?

A directed graph is strongly connected if there is a path between any two pairs of vertices.

### What are weakly connected components?

Weakly connected components refer to a set of vertices in a directed graph where there is a path from each vertex to every other vertex in the set, ignoring the direction of edges.

### Can a graph be both weakly connected and strongly connected?

Yes, it is possible for a directed graph to be both weakly connected and strongly connected. This can happen when the graph has a single strongly connected component or when there are multiple strongly connected components that are all weakly connected to each other.

## Conclusion

In this article, we learned about weakly connected components in a directed graph. We learned that a directed graph G = (V, E)  is weakly connected if it lacks a directed path (from u to v or v to u for any pair of vertices u, v).

We then designed an algorithm to find all the weakly connected components in a directed graph in O(V+E) time.