Я написал код, чтобы найти количество подключенных компонентов направленного графа. Когда я использую приведенную ниже диаграмму в качестве моей матрицы смежности, она дает количество подключенных компонентов как 2 (первый DFS: 0-> 1-> 2, второй DFS : 3).
Но когда я использую приведенную ниже диаграмму в качестве матрицы смежности
Он дает количество подключенных компонентов как 1 (DFS: 0-> 2-> 3-> 1). Итак, я хочу спросить, вычисление количества подключенных компонентов будет зависеть от того, как мы представляем узлы в матрице смежности, если мы используем DFS, чтобы найти количество подключенных компонентов?
Код:
#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;
}