Define a connected component of an undirected graph to be a subgraph where every

Question

Define a connected component of an undirected graph to be a subgraph where every pair of vertices are reachable from each other by traversing through one or more edges within the same subgraph. Show that we can use a depth-first search of an undirected graph G to identify the connected components of G, and that the depth-first forest contains as many trees as G has connected components. More precisely, show how to modify depth-first search so that it assigns to each vertex an integer label cc between 1 and k, where k is the number of connected components of G, such that cc[u] = cc[v] if and only if u and v are in the same connected component. Analyze the running time of your algorithm

Explanation / Answer

As we know, DFS vistis all the nodes one by one and reaches till the depth

Lets say we have a Graph G with 3 Nodes are are connected

A---------B
|
I
C
---> For the Current graph If we run DFS from A , we will get A,B, C or A,C, B both are Valid
which means there is 1 connected Component , If we mark all the nodes as 1 i.e CC[A] = 1
CC[B] = 1 , CC[C] = 1 , because they all are connected and I can visit all Nodes.
Considering The Graph where there is more connected Component

A---------B
|
|
C

K---------L
|
|
M

-------> Suppose we run the DFS starting at A , we will get A, B, C . Which means
In one DFS() call we are able to find one piece of connected component
Then again we have to run DFS starting with K, L or M and we will get another
connected component. So There are 2 connected Component in this Graph
that means K = 2 , so CC[A] = 1 , CC[B] =1 , CC[C] = 1, CC[K] =2 , CC[L] =2 etc

Suppose we have Graph with N , nodes

A B C D , None of the Nodes are connected to each other , So we have to Run DFS() 4 times, to visit all Nodes as in each pass of DFS only 1 Node will be Visited. So there will be 4 connected Component.

Which means we have to run DFS for all the nodes and if they are Visited already they will fall one connected component, Lets say out first example, We have to RUN DFS for all three Nodes A, B, C ..But In first pass only we are able to Visit all the Nodes and There is One connected componet

If the Graph is represented in the form of Adjacency Matrix , As the graph is undirected there will be connection from u-->v as well as v-->u
Our PseudoCode will look like

int connectedComponent = 1;
for(int i=0;i<Nodes;++i){

  for(int j=0;j<Nodes;++j){
   if(visited[i]==false){
   DFS(connectedComponent);
   ++connectedComponent;

}

}

We need to traverse all the nodes , So the Overall time complexity will be
O(NxN) , N is the number of Nodes   

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.