图连通和连通分量

Question

我想知道一个图(连接矩阵)是否只与一个组件相连。当对于所有两个顶点u和v包含从u到v的路径时，图是连通的。我的问题3类型连接(抑制(-1)，非连接(0)，激活(1))我认为如果Aij != 0有连接，我使用DFS来搜索矩阵中有多少分量，但他在某些情况下工作，而不是在其他情况下。

Ex my矩阵(将-1替换为1)：

1, 0, 0, 1, 0,
1, 0, 1, 1, 1,
0, 0, 1, 1, 1,
1, 0, 0, 0, 1,
1, 0, 1, 1, 1,

这里有一个representation of graph。当应用由Wisdom's Wind创建的主题的相同答案(DFS)在2个组件中解决此添加的第39-47行时，是否有办法不使用第39-47行？

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define _MIN -1
#define _MAX 1
#define TAM 5
#define MAX TAM*TAM
#define QNT_MATRIX 1
#define SIZE_MATRIX MAX*QNT_MATRIX

void DFS(int *matrix, int *marks, int vertex, int componentes){
    int i;

    marks[vertex] = componentes;
    for(i=0; i<TAM; i++){
        if(matrix[vertex*TAM+i] != 0){
            if(marks[i] == 0){
                DFS(matrix, marks, i, componentes);
            }
        }
    }
}

int testDFS(int *matrix){
    int marks[TAM];
    int i, k, componentes=0, componentes_total=1;

    memset(marks, 0, TAM*sizeof(int));

    for(i=0; i<TAM; i++){
        if(marks[i] == 0){
            ++componentes;
            DFS(matrix, marks, i, componentes);
        }
    }

    for(i=0; i<TAM-1; i++){//line 39
        for(k=i+1; k<TAM; k++){
            if(marks[i] != marks[k]){
                if(matrix[i*TAM+k] == 0 && matrix[k*TAM+i] == 0){
                    componentes_total++;//no have way connection                
                }
            }
        }
    }//line47
    printf("testDFS Componentes: %d\n", componentes);
    printf("Componentes_total: %d\n", componentes_total);

}

int main(){
    int matrix[SIZE_MATRIX];
    int i;


    srand(time(NULL));

    for(i=0; i<SIZE_MATRIX; i++){
        scanf("%d,", &matrix[i]);
    }
    //Print matrix
    for(i=0; i<SIZE_MATRIX; i++){
        printf("%d ", matrix[i]);
        if((i+1)%TAM==0){
            printf("\n");
        }
        if((i+1)%(MAX)==0){
            printf("\n");
        }
    }

    testDFS(matrix);
    return 0;
}

Answer 1

只需对您的代码稍作调整，它就能完成工作

void DFS(int *matrix, int *marks, int vertex, int& componentes){
int i;

marks[vertex] = componentes;
for(i=0; i<TAM; i++){
    if(matrix[vertex*TAM+i] != 0){
        if(marks[i] == 0){
            DFS(matrix, marks, i, componentes);
        }
        else if(marks[i] != marks[vertex]){
            marks[vertex] = marks[i];
            componentes = marks[i];
        }
    }
}

}

考虑到上面的测试用例，实际上您的代码是right.But的，节点2可以被3,4,5访问，但是节点2不能从任何地方访问。因此，根据您的逻辑，它的连接属性将是2。但是，我添加的检查确保，如果'a‘节点正在访问'b’节点，并且'b‘已经被访问，那么'a’将与'b‘连接，并且具有相同的连接值。