Find Weakly Connected Components in a Directed Graph
Weakly Connected Graph:
A directed graph ‘G = (V, E)’ is weakly connected if the underlying undirected graph Ĝ is connected.
The underlying undirected graph is the graph Ĝ = (V, Ê) where Ê represents the set of undirected edges that is obtained by removing the arrowheads from the directed edges and making them bidirectional in G.
Example:
The directed graph G above is weakly connected since its underlying undirected graph Ĝ is connected.
Weakly Connected Component:
Given a directed graph, a weakly connected component (WCC) is a subgraph of the original graph where all vertices are connected to each other by some path, ignoring the direction of edges.
Example:
In the above directed graph, there are two weakly connected components:
- [0, 1, 2, 3]
- [4, 5]
Algorithm to find Weakly Connected Component:
It uses the algorithm to find connected components of an undirected graph.
- Construct the underlying undirected graph of the given directed graph.
- Find all the connected components of the undirected graph.
- The connected components of the undirected graph will be the weakly connected components of the directed graph.
Implementation:
Below is the code of Weakly Connected Component which takes a directed graph DG as input and returns all the weakly connected components WCC of the input graph.
C++
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Graph { public : int vertices; vector<vector< int > > adjacencyList; Graph( int vertices) { this ->vertices = vertices; adjacencyList.resize(vertices); } void addEdge( int u, int v) { // Use of noEdge(int, int) // prevents duplication of edges if (noEdge(u, v)) { adjacencyList[u].push_back(v); } } // Returns true if there does NOT exist // any edge from u to v bool noEdge( int u, int v) { for ( int destination : adjacencyList[u]) { if (destination == v) { return false ; } } return true ; } }; class WCC { private : Graph directedGraph; public : WCC(Graph directedGraph) : directedGraph(directedGraph) { this ->directedGraph = directedGraph; } // Finds all the connected components // of the given undirected graph vector<vector< int > > connectedComponents(Graph undirectedGraph) { vector<vector< int > > connectedComponents; vector< bool > isVisited(undirectedGraph.vertices, false ); for ( int i = 0; i < undirectedGraph.vertices; i++) { if (!isVisited[i]) { vector< int > component; findConnectedComponent(i, isVisited, component, undirectedGraph); connectedComponents.push_back(component); } } return connectedComponents; } // Finds a connected component // starting from source using DFS void findConnectedComponent( int src, vector< bool >& isVisited, vector< int >& component, Graph undirectedGraph) { isVisited[src] = true ; component.push_back(src); for ( int v : undirectedGraph.adjacencyList[src]) { if (!isVisited[v]) { findConnectedComponent(v, isVisited, component, undirectedGraph); } } } // Step 1: Construct the // underlying undirected graph vector<vector< int > > weaklyConnectedComponents() { Graph undirectedGraph(directedGraph.vertices); for ( int u = 0; u < directedGraph.vertices; u++) { for ( int v : directedGraph.adjacencyList[u]) { undirectedGraph.addEdge(u, v); undirectedGraph.addEdge(v, u); } } // Step 2: Find the connected components // of the undirected graph return connectedComponents(undirectedGraph); } }; // Driver code int main() { Graph directedGraph(6); directedGraph.addEdge(0, 1); directedGraph.addEdge(0, 2); directedGraph.addEdge(3, 1); directedGraph.addEdge(3, 2); directedGraph.addEdge(4, 5); WCC wcc(directedGraph); vector<vector< int > > weaklyConnectedComponents = wcc.weaklyConnectedComponents(); int index = 1; for (vector< int > component : weaklyConnectedComponents) { cout << "Component " << index++ << ": " ; for ( int i : component) { cout << i << " " ; } cout << endl; } return 0; } |
Java
// Java Code for the above algorithm import java.util.ArrayList; class Graph { int vertices; ArrayList<ArrayList<Integer> > adjacencyList; public Graph( int vertices) { this .vertices = vertices; adjacencyList = new ArrayList<>(vertices); for ( int i = 0 ; i < this .vertices; i++) adjacencyList.add( new ArrayList<>()); } public void addEdge( int u, int v) { // Use of noEdge(int, int) // prevents duplication of edges if (noEdge(u, v)) adjacencyList.get(u).add(v); } // Returns true if there does NOT exist // any edge from u to v boolean noEdge( int u, int v) { for ( int destination : adjacencyList.get(u)) if (destination == v) return false ; return true ; } } class WCC { private final Graph directedGraph; public WCC(Graph directedGraph) { this .directedGraph = directedGraph; } // Finds all the connected components // of the given undirected graph private ArrayList<ArrayList<Integer> > connectedComponents(Graph undirectedGraph) { ArrayList<ArrayList<Integer> > connectedComponents = new ArrayList<>(); boolean [] isVisited = new boolean [undirectedGraph.vertices]; for ( int i = 0 ; i < undirectedGraph.vertices; i++) { if (!isVisited[i]) { ArrayList<Integer> component = new ArrayList<>(); findConnectedComponent(i, isVisited, component, undirectedGraph); connectedComponents.add(component); } } return connectedComponents; } // Finds a connected component // starting from source using DFS private void findConnectedComponent( int src, boolean [] isVisited, ArrayList<Integer> component, Graph undirectedGraph) { isVisited[src] = true ; component.add(src); for ( int v : undirectedGraph.adjacencyList.get(src)) if (!isVisited[v]) findConnectedComponent(v, isVisited, component, undirectedGraph); } public ArrayList<ArrayList<Integer> > weaklyConnectedComponents() { // Step 1: Construct the // underlying undirected graph Graph undirectedGraph = new Graph(directedGraph.vertices); for ( int u = 0 ; u < directedGraph.vertices; u++) { for ( int v : directedGraph.adjacencyList.get(u)) { undirectedGraph.addEdge(u, v); undirectedGraph.addEdge(v, u); } } // Step 2: Find the connected components // of the undirected graph return connectedComponents(undirectedGraph); } } public class WCCDemo { // Driver Code public static void main(String[] args) { Graph directedGraph = new Graph( 6 ); directedGraph.addEdge( 0 , 1 ); directedGraph.addEdge( 0 , 2 ); directedGraph.addEdge( 3 , 1 ); directedGraph.addEdge( 3 , 2 ); directedGraph.addEdge( 4 , 5 ); ArrayList<ArrayList<Integer> > weaklyConnectedComponents = new WCC(directedGraph) .weaklyConnectedComponents(); int index = 1 ; for (ArrayList<Integer> component : weaklyConnectedComponents) { System.out.print( "Component " + index++ + ": " ); for (Integer i : component) System.out.print(i + " " ); System.out.println(); } } } |
Python3
# Python3 code for the above algorithm from typing import List class Graph: def __init__( self , vertices: int ): self .vertices = vertices self .adjacency_list = [[] for _ in range (vertices)] # Use of NoEdge(int, int) #prevents duplication of edges def add_edge( self , u: int , v: int ): if self .no_edge(u, v): self .adjacency_list[u].append(v) # Returns true if there does NOT exist # any edge from u to v def no_edge( self , u: int , v: int ): return v not in self .adjacency_list[u] class WCC: def __init__( self , directed_graph: Graph): self .directed_graph = directed_graph # Finds all the connected components # of the given undirected graph def connected_components( self , undirected_graph: Graph): connected_components = [] is_visited = [ False for _ in range (undirected_graph.vertices)] for i in range (undirected_graph.vertices): if not is_visited[i]: component = [] self .find_connected_component(i, is_visited, component, undirected_graph) connected_components.append(component) return connected_components # Finds a connected component # starting from source using DFS def find_connected_component( self , src: int , is_visited: List [ bool ], component: List [ int ], undirected_graph: Graph): is_visited[src] = True component.append(src) for v in undirected_graph.adjacency_list[src]: if not is_visited[v]: self .find_connected_component(v, is_visited, component, undirected_graph) def weakly_connected_components( self ): #Step 1: Construct the # underlying undirected graph undirected_graph = Graph( self .directed_graph.vertices) for u in range ( self .directed_graph.vertices): for v in self .directed_graph.adjacency_list[u]: undirected_graph.add_edge(u, v) undirected_graph.add_edge(v, u) # Step 2: Find the connected components # of the undirected grap return self .connected_components(undirected_graph) #Driver code def main(): directed_graph = Graph( 6 ) directed_graph.add_edge( 0 , 1 ) directed_graph.add_edge( 0 , 2 ) directed_graph.add_edge( 3 , 1 ) directed_graph.add_edge( 3 , 2 ) directed_graph.add_edge( 4 , 5 ) weakly_connected_components = WCC(directed_graph).weakly_connected_components() for index, component in enumerate (weakly_connected_components, start = 1 ): print ( "Component {}: {}" . format (index, component)) if __name__ = = "__main__" : main() |
C#
// C# Code for the above algorithm using System; using System.Collections.Generic; class Graph { public int vertices; public List<List< int > > adjacencyList; public Graph( int vertices) { this .vertices = vertices; adjacencyList = new List<List< int > >(vertices); for ( int i = 0; i < this .vertices; i++) adjacencyList.Add( new List< int >()); } public void AddEdge( int u, int v) { // Use of NoEdge(int, int) // prevents duplication of edges if (NoEdge(u, v)) adjacencyList[u].Add(v); } // Returns true if there does NOT exist // any edge from u to v bool NoEdge( int u, int v) { foreach ( int destination in adjacencyList[u]) if (destination == v) return false ; return true ; } } class WCC { private readonly Graph directedGraph; public WCC(Graph directedGraph) { this .directedGraph = directedGraph; } // Finds all the connected components // of the given undirected graph private List<List< int > > ConnectedComponents(Graph undirectedGraph) { List<List< int > > connectedComponents = new List<List< int > >(); bool [] isVisited = new bool [undirectedGraph.vertices]; for ( int i = 0; i < undirectedGraph.vertices; i++) { if (!isVisited[i]) { List< int > component = new List< int >(); FindConnectedComponent(i, isVisited, component, undirectedGraph); connectedComponents.Add(component); } } return connectedComponents; } // Finds a connected component // starting from source using DFS private void FindConnectedComponent( int src, bool [] isVisited, List< int > component, Graph undirectedGraph) { isVisited[src] = true ; component.Add(src); foreach ( int v in undirectedGraph .adjacencyList[src]) if (!isVisited[v]) FindConnectedComponent(v, isVisited, component, undirectedGraph); } public List<List< int > > WeaklyConnectedComponents() { // Step 1: Construct the // underlying undirected graph Graph undirectedGraph = new Graph(directedGraph.vertices); for ( int u = 0; u < directedGraph.vertices; u++) { foreach ( int v in directedGraph.adjacencyList[u]) { undirectedGraph.AddEdge(u, v); undirectedGraph.AddEdge(v, u); } } // Step 2: Find the connected components // of the undirected graph return ConnectedComponents(undirectedGraph); } } class Program { // Driver Code static void Main( string [] args) { Graph directedGraph = new Graph(6); directedGraph.AddEdge(0, 1); directedGraph.AddEdge(0, 2); directedGraph.AddEdge(3, 1); directedGraph.AddEdge(3, 2); directedGraph.AddEdge(4, 5); List<List< int > > weaklyConnectedComponents = new WCC(directedGraph) .WeaklyConnectedComponents(); int index = 1; foreach (List< int > component in weaklyConnectedComponents) { Console.Write( "Component " + index++ + ": " ); foreach ( int i in component) Console.Write(i + " " ); Console.WriteLine(); } } } // This code is contributed by lokeshpotta20. |
Javascript
// JavaScript Code for the above algorithm class Graph { constructor(vertices) { this .vertices = vertices; this .adjacencyList = new Array(vertices); for (let i = 0; i < vertices; i++) { this .adjacencyList[i] = []; } } addEdge(u, v) { // Use of noEdge(int, int) // prevents duplication of edges if ( this .noEdge(u, v)) { this .adjacencyList[u].push(v); } } // Returns true if there does NOT // exist any edge from u to v noEdge(u, v) { for (let destination of this .adjacencyList[u]) { if (destination === v) { return false ; } } return true ; } } class WCC { constructor(directedGraph) { this .directedGraph = directedGraph; } // Finds all the connected components // of the given undirected graph connectedComponents(undirectedGraph) { const connectedComponents = []; const isVisited = Array(undirectedGraph.vertices).fill( false ); for (let i = 0; i < undirectedGraph.vertices; i++) { if (!isVisited[i]) { const component = []; this .findConnectedComponent(i, isVisited, component, undirectedGraph); connectedComponents.push(component); } } return connectedComponents; } // Finds a connected component // starting from source using DFS findConnectedComponent(src, isVisited, component, undirectedGraph) { isVisited[src] = true ; component.push(src); for (let v of undirectedGraph.adjacencyList[src]) { if (!isVisited[v]) { this .findConnectedComponent(v, isVisited, component, undirectedGraph); } } } weaklyConnectedComponents() { // Step 1: Construct the // underlying undirected graph const undirectedGraph = new Graph( this .directedGraph.vertices); for (let u = 0; u < this .directedGraph.vertices; u++) { for (let v of this .directedGraph.adjacencyList[u]) { undirectedGraph.addEdge(u, v); undirectedGraph.addEdge(v, u); } } // Step 2: Find the connected // components of the undirected graph return this .connectedComponents(undirectedGraph); } } const directedGraph = new Graph(6); directedGraph.addEdge(0, 1); directedGraph.addEdge(0, 2); directedGraph.addEdge(3, 1); directedGraph.addEdge(3, 2); directedGraph.addEdge(4, 5); const weaklyConnectedComponents = new WCC(directedGraph).weaklyConnectedComponents(); let index = 1; for (let component of weaklyConnectedComponents) { console.log(`Component ${index++}: ${component.join( " " )}`); } // This code is contributed by karthik. |
Component 1: 0 1 3 2 Component 2: 4 5
Time complexity: O(V+E)