c - 連結成分数の問い合わせ

Question

有向グラフの連結成分の数を見つけるコードを書きました。以下のダイアグラムを隣接行列として使用すると、連結成分の数が 2 になります (最初の DFS: 0->1->2、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;

}

Answer 1

自明でない強連結成分 (SCC) がグラフにない。(頂点からそれ自体へのパスはありません。)したがって、「1」と「2」という答えはどちらも間違っています。正解は4つです。

あなたのアルゴリズムは SCC を見つけません。アルゴリズムは無向グラフで連結成分を見つけることができますが、いずれかの端からエッジを見つける必要があるため、グラフを無向にするために隣接リストを変更する必要があります。