Запрос о количестве подключенных компонентов

Я написал код, чтобы найти количество подключенных компонентов направленного графа. Когда я использую приведенную ниже диаграмму в качестве моей матрицы смежности, она дает количество подключенных компонентов как 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;

}

person Abhi Jain    schedule 30.05.2016    source источник


Ответы (1)


В вашем графе нет нетривиальных сильно связанных компонентов (SCC). (Нет пути из любой вершины в саму себя.) Таким образом, оба ответа «один» и «два» неверны; правильный ответ четыре.

Ваш алгоритм не находит SCC. Алгоритм может найти связанные компоненты в неориентированном графе, но ваш список смежности должен быть изменен, чтобы сделать граф неориентированным, поскольку вам нужно найти ребро с любого конца.

person rici    schedule 30.05.2016
comment
Моя ошибка. Я написал Strongly Connected Components вместо Connected Components. Да, алгоритм предназначен для количества связанных компонентов в ориентированном графе, а не для сильно связанных компонентов. Но как четыре? - person Abhi Jain; 30.05.2016
comment
Я не уверен, есть ли смысл говорить о компоненте связности ориентированного графа. Как бы вы это определили? Что бы это ни значило, ваш алгоритм не вычисляет его. Ваш алгоритм будет вычислять связные компоненты неориентированного графа, что является четко определенной концепцией. - person rici; 31.05.2016
comment
Спасибо за объяснение. - person Abhi Jain; 31.05.2016