CODEWITHSUNDEEP
cgraph-theorydepth-first-searchconnected-components
Abhi Jain
Abhi Jain

Reputation: 35

Query about number of Connected Components

I have written the code to find the number of Connected Components of Directed Graph.When I use the Diagram below as my Adjacency Matrix.It gives the number of Connected Components as 2(First DFS: 0->1->2,Second DFS: 3).

enter image description here

But when I use the Diagram below as my Adjacency Matrix

enter image description here

It gives the number of Connected Components as 1(DFS: 0->2->3->1).So what I want to ask is calculating the number of Connected Components will depend on how we represent nodes in Adjacency Matrix if we use DFS to find the number of Connected Components?

Code:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

struct Graph
{
    int V;
    int E;
    int **Adj;
};


void AdjacencyMatrixOfGraph(struct Graph *G)
{
    int u,v,i,j,w;
    scanf("%d %d",&G->E,&G->V);
    G->Adj = (int**)malloc(G->V*sizeof(int *));
    for(i=0;i<G->V;i++)
    {
        G->Adj[i] = (int*)malloc(G->V*sizeof(int));
    }
    for(i=0;i<G->V;i++)
    {
        for(j=0;j<G->V;j++)
        {
            G->Adj[i][j] = 0;
        }

    }
    for(i=0;i<G->E;i++)
    {
        scanf("%d %d",&u,&v);
        G->Adj[u][v] = 1;
        //G->Adj[v][u] = 1;
    }
}
int Visited[1000];
void DFS(struct Graph *G,int u,int Visited[])
{
    Visited[u]=1;
    int v,w,i;
    for(v=0;v<G->V;v++)
    {
        if(G->Adj[u][v] !=0 && Visited[v] == 0)
        {
            //printf("U is %d and V is %d\n",u,v);
            Visited[v] = 1;
            DFS(G,v,Visited);
        }
    }

}

void DFSTraversal(struct Graph *G)
{
    //int Visited[G->V];
    int i;
    int counter = 0;
    for(i=0;i<G->V;i++)
    {
        Visited[i] = 0;
    }
    for(i=0;i<G->V;i++)
    {
        if(!Visited[i])
        {
            DFS(G,i,Visited);
            counter++;
        }
    }
    printf("The Number of Connected Components is %d\n",counter);
}
int main()
{

    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
    AdjacencyMatrixOfGraph(graph);
    DFSTraversal(graph);
    return 0;

}

Upvotes: 0

Views: 426

Answers (1)

rici
rici

Reputation: 241861

There are no non-trivial Strongly Connected Components (SCCs) in your graph. (There is no path from any vertex to itself.) So both of the answers "one" and "two" are wrong; the correct answer is four.

Your algorithm does not find SCCs. The algorithm could find Connected Components in an undirected graph, but your adjacency list would need to be modified to make the graph undirected, since you need to find the edge from either end.

Upvotes: 0

Related Questions