Find the Connected Component in the Undirected Graph Solution
Connected Components in an undirected graph
Given an undirected graph, print all connected components line by line. For example consider the following graph.
We strongly recommend to minimize your browser and try this yourself first.
We have discussed algorithms for finding strongly connected components in directed graphs in following posts.
Kosaraju's algorithm for strongly connected components.
Tarjan's Algorithm to find Strongly Connected Components
Finding connected components for an undirected graph is an easier task. We simple need to do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components. Below are steps based on DFS.
1) Initialize all vertices as not visited. 2) Do following for every vertex 'v'. (a) If 'v' is not visited before, call DFSUtil(v) (b) Print new line character DFSUtil(v) 1) Mark 'v' as visited. 2) Print 'v' 3) Do following for every adjacent 'u' of 'v'. If 'u' is not visited, then recursively call DFSUtil(u)
Below is the implementation of above algorithm.
C++
#include<iostream>
#include <list>
using namespace std;
class Graph
{
int V;
list< int > *adj;
void DFSUtil( int v, bool visited[]);
public :
Graph( int V);
void addEdge( int v, int w);
void connectedComponents();
};
void Graph::connectedComponents()
{
bool *visited = new bool [V];
for ( int v = 0; v < V; v++)
visited[v] = false ;
for ( int v=0; v<V; v++)
{
if (visited[v] == false )
{
DFSUtil(v, visited);
cout << " " ;
}
}
}
void Graph::DFSUtil( int v, bool visited[])
{
visited[v] = true ;
cout << v << " " ;
list< int >::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
Graph::Graph( int V)
{
this ->V = V;
adj = new list< int >[V];
}
void Graph::addEdge( int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
int main()
{
Graph g(5);
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
cout << "Following are connected components " ;
g.connectedComponents();
return 0;
}
/div>
Java
import java.util.LinkedList;
class Graph {
int V;
LinkedList<Integer>[] adjListArray;
Graph( int V) {
this .V = V;
adjListArray = new LinkedList[V];
for ( int i = 0 ; i < V ; i++){
adjListArray[i] = new LinkedList<Integer>();
}
}
void addEdge( int src, int dest) {
adjListArray[src].add(dest);
adjListArray[dest].add(src);
}
void DFSUtil( int v, boolean [] visited) {
visited[v] = true ;
System.out.print(v+ " " );
for ( int x : adjListArray[v]) {
if (!visited[x]) DFSUtil(x,visited);
}
}
void connectedComponents() {
boolean [] visited = new boolean [V];
for ( int v = 0 ; v < V; ++v) {
if (!visited[v]) {
DFSUtil(v,visited);
System.out.println();
}
}
}
public static void main(String[] args){
Graph g = new Graph( 5 );
g.addEdge( 1 , 0 );
g.addEdge( 2 , 3 );
g.addEdge( 3 , 4 );
System.out.println( "Following are connected components" );
g.connectedComponents();
}
}
Python 3
class Graph:
def __init__( self ,V):
self .V = V
self .adj = [[] for i in range (V)]
def DFSUtil( self , temp, v, visited):
visited[v] = True
temp.append(v)
for i in self .adj[v]:
if visited[i] = = False :
temp = self .DFSUtil(temp, i, visited)
return temp
def addEdge( self , v, w):
self .adj[v].append(w)
self .adj[w].append(v)
def connectedComponents( self ):
visited = []
cc = []
for i in range ( self .V):
visited.append( False )
for v in range ( self .V):
if visited[v] = = False :
temp = []
cc.append( self .DFSUtil(temp, v, visited))
return cc
if __name__ = = "__main__" :
g = Graph( 5 );
g.addEdge( 1 , 0 )
g.addEdge( 2 , 3 )
g.addEdge( 3 , 4 )
cc = g.connectedComponents()
print ( "Following are connected components" )
print (cc)
C#
using System;
using System.Collections.Generic;
public class Graph
{
int V;
List< int >[] adjListArray;
Graph( int V)
{
this .V = V;
adjListArray = new List< int >[V];
for ( int i = 0; i < V ; i++)
{
adjListArray[i] = new List< int >();
}
}
void addEdge( int src, int dest)
{
adjListArray[src].Add(dest);
adjListArray[dest].Add(src);
}
void DFSUtil( int v, bool [] visited)
{
visited[v] = true ;
Console.Write(v+ " " );
foreach ( int x in adjListArray[v])
{
if (!visited[x]) DFSUtil(x,visited);
}
}
void connectedComponents()
{
bool [] visited = new bool [V];
for ( int v = 0; v < V; ++v)
{
if (!visited[v])
{
DFSUtil(v,visited);
Console.WriteLine();
}
}
}
public static void Main(String[] args)
{
Graph g = new Graph(5);
g.addEdge(1, 0);
g.addEdge(2, 3);
g.addEdge(3, 4);
Console.WriteLine( "Following are connected components" );
g.connectedComponents();
}
}
Output:
0 1 2 3 4
Time complexity of above solution is O(V + E) as it does simple DFS for given graph.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
0 1
You Might Also Like
Subscribe to Our Newsletter
Find the Connected Component in the Undirected Graph Solution
Source: https://tutorialspoint.dev/data-structure/graph-data-structure/connected-components-in-an-undirected-graph