Finding connected components using DFS
Ok now that we are thorough with Connected Components and Strongly Connected components. Let's check how to find the connected components using DFS.
For finding the components we follow the following steps
STEP 1:
Take an array consisting of all the vertices. That is the size of array = number of vertices.
STEP 2:
Assign each vertex value in the array as -1
STEP 3:
Start from each vertex and apply DFS to them if and only if vertex value=-1 Else move to the next vertex.
STEP 4:
At last count, the number of times DFS moves was initiated from the parent loop. That many are the components and each component is the vertices traversed during DFS.
Let's create an algorithm to justify my point.
void Connected_components(int v,int *G)
{
int c=0,i;
int arr=new int[v];
for (i=0;i<v;i++)
{
arr[i]=-1;
}
for (i=0;i<v;i++)
{
if(arr[i]==-1)
{
c++;
printf("\n");
DFS(i,v,G);
}
}
printf("Number of components:%d",c);
}
void DFS(int s,int v,int *G)
{
for(i=s;i<v;i++)
{
printf("%d-",G->value);
G->value=0;
if(G->next->value!=NULL and G->next->value=-1)
DFS(s+1,v.G->next);
}
}
Now that we have devised an algorithm. Let's take an example and solve it.
Let us take the graph below and find the number of components also each component values
As shown here we have a partly connected and partly disconnected undirected graph.
We need to find the number of components and the contents of each component respectively.
Before starting I must briefly tell about the 'G' variable in the algorithm.
G is a self-referential pointer. G points to a structure which is defined as follows
typedef struct depth
{
int value;
depth *next
};
Now let's apply step 1 and convert each vertex value to -1.
AFTER APPLYING STEP 1 the graph looks like
Thus as shown each value is -1.
Now we choose our first vertex as 0. Though any vertex can be chosen. Yet let us go serially. hence, let us choose '0' vertex.
Thus, we start performing DFS from 0.
First, c=0 becomes c=c+1 which is '1'
Hence, 0 is printed on the screen and DFS() is called again
Now we change the value of '0' vertex to 0 and move to 2.
ON THE SCREEN
0-
After 2 it goes to next neighbor using DFS() which is 4 after changing the value of '2' vertex as 0
ON THE SCREEN NOW WE GET
0-2-
Now when 2 is also completed let us move to 4 and makes it 0
ON THE SCREEN DISPLAY
0-2-4-
Now the DFS cannot send it to any other node hence, it moves out of the DFS() to the parent function which is connected components().
Again now the connected components loop moves to '1' vertex and finds that it is still -1 so c++ gets executed and c becomes'2'. Also, DFS() is called.
Thus, '1' vertex value gets changed to 0.
ON THE SCREEN NOW IT DISPLAYS
0-2-4-
1-
DFS() gets called again and the pointer moves to 3 now.
Hence, now the graph becomes
ON THE SCREEN NOW IT DISPLAYS
0-2-4-
1-3-
Now since DFS() cannot connect to any other node, it retraces back to the parent function.
Now in the connected components loop, the '2' vertex is visited but DFS cannot be called as the value is no more '-1'
Similarly, loop visits vertex '3' and vertex '4' but DFS could not be called as the values are not '-1' in respective nodes.
Hence c value also does not increase.
Now when our loop points to vertex '5' Now it is still -1 hence c value increases to 3 from 2 and the new line is printed.
Thus DFS() is called
And finally, vertex '5' is visited.
ON THE SCREEN IT DISPLAYS
0-2-4-
1-3-
5-
Now since DFS cannot go to any other node hence it breaks out.
In the parent function loop points to vertex '5'. But since its value is not '-1' hence, DFS() not called.
Then the loop becomes 6 and breaks out of the parent loop
Then it prints 3 which is the number of components
Finally the output of the code on the screen
0-2-4-
1-3-
5-
Number of components:3
No comments:
Post a Comment