Abfrage über die Anzahl der verbundenen Komponenten

Question

Ich habe den Code geschrieben, um die Anzahl der verbundenen Komponenten des gerichteten Graphen zu finden.Wenn ich das Diagramm unten als meine Adjacency Matrix.It gibt die Anzahl der verbundenen Komponenten als 2 (Erste DFS: 0 -> 1-> 2, zweites DFS: 3).

Aber wenn ich den Diagramm unten als meine Adjazenzmatrix

es die Anzahl der Connected Components gibt als 1 (DFS: 0-> 2-> 3-> 1). Was ich fragen möchte, ist die Berechnung der Anzahl der verbundenen Komponenten hängt davon ab, wie wir Knoten in Adjazenz-Matrix darstellen, wenn wir DFS verwenden, um die Anzahl der verbundenen Komponenten zu finden?

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; 

} 

Answer 1

Es gibt keinen nicht-trivialen stark verbundenen Bauteile (SVB) in Ihrem Diagramm. (Es gibt keinen Weg von irgendeinem Eckpunkt zu sich selbst.) Also sind beide Antworten "Eins" und "Zwei" falsch; Die richtige Antwort ist vier.

Ihr Algorithmus findet keine SCCs. Der Algorithmus könnte Connected Components in einem ungerichteten Graphen finden, aber Ihre Adjazenzliste müsste geändert werden, um das Diagramm ungerichtet zu machen, da Sie die Kante von jedem Ende aus finden müssen.