Connected components in undirected graph

• connected components in a undirected graph is a subgraph in which each pair of node in the subgraph have path between them .

Algorithm

ConnectedComponent(){
1. initialized all vertices as unchecked
2. for all vertices
    - if not checked than apply dfs by calling dfs(v,checked[]) function .
}

dfs(v,checked[]){
1. mark v as checked and diaplay it
2. for neighbouring vertex 
   - if not checked apply dfs to unchecked neighbouring vertex
}

Properties

• Time Complexity: O(V+E), where V is the number of vertices and E is total number edges in a graph.
• Space Complexity: O(n) , where n is total number of vertices in graph .

Advantages

• use in the social networking sites, connected components are used to depict the group of people who are friends of each other or who have any common interest
• It can also be used to convert a graph into a Direct Acyclic graph of strongly connected components .

Adjacency Matrix

adjacency matrix is a matrix that maintain the information of adjacent vertices .

• A(i,j)= { 1 if there is a edge from vertex i to vertex j and 0 if there is no edge from vertex i to vertex j }

• Undirected Graph

• Directed Graph

Algorithm

1. Initialized a 2D array Adj[][] globally .
   • if undirected than n*(n-1)/2
   • else n*(n-1)
2. For each edge in adj[][], Update value at Adj[X][Y] to 1 and
   • if undirected graph than Adj[Y][X] to 1
   • denotes that there is a edge between X and Y.
3. Display the Adjacency Matrix after the above operation for all the pairs in adj[][].

Properties