使用深度优先搜索计算邻接矩阵表示的不同图数的 C 程序

Question

下面的代码对邻接矩阵的所有元素使用深度优先搜索来计算邻接矩阵中表示的图的数量。

出于某种原因，此代码仅适用于某些测试用例，但不适用于其他测试用例，我想修复此问题。

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

//depth-first search
void dfs(int start, int n, int * visited, int ** family){
    int current;
    visited[start] = 1;
    for(current=0;current<n;++current)
        if(visited[current] == 0 && family[start][current] == 1) dfs(current, n, visited, family);
}

//set all visited[i] array integers to zero
void zero(int n, int * visited){
    int i;
    for(i=0;i<n;++i){
        visited[i] = 0;
    }
}

int main(){
    int ** family;
    int * visited;
    int ** all_visited;
    int n, k;
    int i, j, x, y;
    int counter = 0;
    int familycount = 0;

    // n == number of elements
    // k == number of lines to be read
    scanf("%i %i", &n, &k);

    //memory allocation
    family = (int**) malloc(sizeof(int*) * n);
    for(i=0;i<n;++i){
        family[i] = (int*) malloc(sizeof(int) * n);
    }
    all_visited = (int**) malloc(sizeof(int*) * n);
    for(i=0;i<n;++i){
        all_visited[i] = (int*) malloc(sizeof(int) * n);
    }

    visited = (int*) malloc(sizeof(int) * n);
    zero(n, visited);

    //receive input pairs and build adjacency matrix for the graph
    for(i=0;i<k;++i){
        scanf("%i %i", &x, &y);
        --x;
        --y;
        family[x][y] = 1;
    }

    //Perform depth-first search for each element in adjacency matrix.
    //If dfs() returns a visited[] array that has never been seen before,
    // add +1 to familycount.
    for(i=0;i<n;++i){
            dfs(i,n,visited,family);
            for(j=0;j<n;++j){
                all_visited[i][j] = visited[j];
            }
            for(x=0;x<i;++x){
                for(y=0;y<n;++y){
                    if(all_visited[x][y] == 1 && visited[y] == 1) break;
                }
                if(y == n) ++counter;
            }
            if(counter == i ) ++familycount;
            zero(n, visited);
            counter = 0;
        }
    printf("%i\n",familycount);
    return 0;
}

例如，如果我们采用以下测试用例:

9 8
1 2
2 3
3 6
4 3
6 5
7 8
1 4
6 2

第一行 ("9 8") 表示我们有九个可能的元素(从 1 到 9 的整数)，下面是八行输入。

可能 表示我可能会或可能不会输入 9 个顶点，但绝不会超过 9 个。如果我不输入一个顶点，它将被忽略。

以下所有行的意思是“X 与 Y 相关”、“X 与 Y 属于同一个家族”，或者更正式地说，“X 和 Y 属于同一个图”。

如下所示，这个测试用例有两个族或两个图，所以程序输出应该是“2”。

Answer 1

此代码比您要解决的问题要昂贵得多。

这个问题在图论中被称为图连通性，您可以通过对每个节点进行简单的 DFS 来解决它；然后我们将使用 visited数组作为当前DFS探索的存储。

对于任何顶点 v:

• visited[v] = 0 <--> v还没有探索过

• visited[v] < 0 <--> v正在进行探索，但尚未完成

• visited[v] > 0 <--> v探索完毕

从 v 开始，我们将使用相同的持续计数器值标记它的每个可到达顶点，一旦 DFS 返回，我们将简单地交换 visited[v] 的符号。值，意味着它的探索现在已经结束。

要得到不连通图的个数，只需要统计visited中有多少个不同的值即可数组。

代码如下:

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

void dfs(int start, int n, int *visited, int **family, int counter) {
    if (visited[start] > 0)
        return;
    else if (visited[start] == 0)
        visited[start] = -counter;

    for (int i = 0; i < n; i++) {
        if (family[start][i] == 1 && visited[i]==0) {
            dfs(i, n, visited, family, counter);
        }
    }
    visited[start] = -visited[start];

    return;
}

//set all visited[i] array integers to zero
void zero(int n, int * visited) {
    int i;
    for (i = 0; i<n; ++i) {
        visited[i] = 0;
    }
}

int main() {
    int ** family;
    int * visited;
    int n, k;
    int i, x, y;
    int counter = 1;
    int familycount = 0;
    int last = -1;

    // n == number of elements
    // k == number of lines to be read
    printf("Insert vertex# and edge#\n");
    scanf("%i %i", &n, &k);

    //memory allocation
    family = (int**)malloc(sizeof(int*) * n);
    for (i = 0; i<n; ++i) {
        family[i] = (int*)malloc(sizeof(int) * n);
    }

    visited = (int*)malloc(sizeof(int) * n);
    zero(n, visited);

    //receive input pairs and build adjacency matrix for the graph
    printf("Now insert all the edges, once at time\nFor edge (a,b), insert a b and press Enter\n");
    for (i = 0; i<k; ++i) {
        scanf("%i %i", &x, &y);
        --x;
        --y;
        family[x][y] = 1;
    }

    zero(n, visited);

    //Perform depth-first search for each element in adjacency matrix.
    //If dfs() returns a visited[] array that has never been seen before,
    // add +1 to familycount.
    for (i = 0; i<n; ++i) {
        dfs(i,n,visited,family,counter);
        counter++;
    }

    for (i = 0; i < n; i++) {
        if (visited[i] != last) {
            familycount++;
            last = visited[i];
        }
    }

    printf("Graph #: %i\n", familycount);
    return 0;
}

而不是给出 9 8作为第一个输入，您需要输入 8 8 ，分别表示8个顶点和8条边。