图连通和连通分量

Question

我想发现一个图（连接矩阵）是否只与一个组件连接。当所有两个顶点 u 和 v 都包含从 u 到 v 的路径时，该图是连通的。我的问题 3 类型连接（抑制（-1），非连接（0），激活（1））我想如果 Aij != 0 有连接我使用 DFS 来搜索矩阵中有多少组件但他适用于某些情况而不是对其他人。

Ex 我的矩阵（将 -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. When applies the same answer (DFS) of topic created by Wisdom's Wind 导致 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' 连接并且具有相同的连接值。

图连通和连通分量

Graph connected and Connected component

c++

graph

depth-first-search