Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
2.
Problem
3.
Solution
3.1.
Idea: 
3.2.
Algorithm:
3.3.
Implementation in Java
4.
Frequently Asked Questions
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

Author 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.

Weakly Connected Components in a Directed Graph

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.

Weakly Connected:  A directed graph G is weakly connected if it lacks a directed path (from u to v or v to u for any pair of vertices u, v).

 

In other words, draw an undirected graph G` of G whose edges are obtained by removing the arrowheads from the edges in G and making them bidirectional.

If G` is connected, we can say that G is weakly connected.

 

In a connected graph, each node is reachable from every other node.

 

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

import java.util.ArrayList;

class Graph {

    ArrayList<ArrayList<Integer> > adjacencyList;
    int vertices;
    
    public Graph(int vertices)
    {
        this.vertices = vertices;
        adjacencyList = new ArrayList<>(vertices);

        for (int i = 0; i < this.vertices; ++i)
            adjacencyList.add(new ArrayList<>());
    }

    // Returns true if there is no edge from u to v.
    boolean noEdge(int u, int v)
    {
        for (int dest : adjacencyList.get(u))
            if (dest == v)
                return false;
        return true;
    }

    public void addEdge(int u, int v)
    {
        if (noEdge(u, v)){
            adjacencyList.get(u).add(v);
        }
    }
}

class WCC {
    private final Graph directedGraph;

    public WCC(Graph directedGraph)
    {
        this.directedGraph = directedGraph;
    }

    // Finds all the connected components of the created undirected graph.
    private ArrayList<ArrayList<Integer> > connectedComponents(Graph undirectedGraph)
    {
        ArrayList<ArrayList<Integer> > connectedComponent = new ArrayList<>();
        boolean[] visited = new boolean[undirectedGraph.vertices];

        for (int i = 0; i < undirectedGraph.vertices; i++) {
            if (!visited[i]) {
                ArrayList<Integer> component = new ArrayList<>();
                findConnectedComponent(i, visited, component, undirectedGraph);
                connectedComponent.add(component);
            }
        }

    return connectedComponent;
    }

    // Use DFS to find a connected component starting from the source.
    private void findConnectedComponent(int src, boolean[] visited, ArrayList<Integer> component, Graph undirectedGraph)
    {
        visited[src] = true;
        component.add(src);

        for (int vertex : undirectedGraph.adjacencyList.get(src))
            if (!visited[vertex])
                findConnectedComponent(vertex, visited, component, undirectedGraph);
    }

    public ArrayList<ArrayList<Integer> > weaklyConnectedComponents()
    {
        // 1. Construct the corresponding undirected graph.
        Graph undirectedGraph = new Graph(directedGraph.vertices);
        for (int i = 0; i < directedGraph.vertices; i++) {
            for (int v : directedGraph.adjacencyList.get(i)) {
                undirectedGraph.addEdge(i, v);
                undirectedGraph.addEdge(v, i);
            }
        }

    // 2. Find the connected components of the created undirected graph.
        return connectedComponents(undirectedGraph);
    }
}

public class CC{

    public static void main(String[] args)
    {
        Graph G = new Graph(7);

        G.addEdge(0, 1);
        G.addEdge(1, 2);
        G.addEdge(2, 3);
        G.addEdge(3, 4);
        G.addEdge(5, 6);

        ArrayList<ArrayList<Integer> >WCCs = new WCC(G).weaklyConnectedComponents();

        int index = 1;
        for (ArrayList<Integer> components : WCCs) {
            System.out.print("Component " + index++ + ": ");
            for (Integer i : components)
                System.out.print(i + " ");
            System.out.println();
        }
    }
}

 

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

Frequently Asked Questions

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.

Recommended Readings:

Apart from that, use Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It helps you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Previous article
Max Flow Problem
Next article
Implementations and Applications of Karger’s Algorithm for Minimum Cut
Live masterclass