c - 如何确定特定节点是否找到所有其他节点？

Question

所以我试图确定是否可以找到一个可用于查找某个图中的所有其他节点的特定节点。我在 C 中做了一些伪代码。在使用深度优先搜索时，我无法确定如何检查访问的节点。

#include<stdio.h>

int n;
int Graph[n][n];
int visited[n];

int main (int argc, char *argv[]){

    int i;
    int j;
    int x = 1;

    for (i=0; i < n; i++){ // run DFS on all variables to determine if any one node implies all others
        DFS(i) // starting node/variable

        for (j=0; j<n; j++){
            if (visited[j]==0){ // has not been visited
                x = 0; // boolean int variable set to 0
            }
        }

        if (x!=0){ // if all variables are visited, x will be equal to 1
            printf("This variable implies all others");
            return i;
        }
    }
    printf("No variables imply all others");
    return -1;
}


int DFS(int i)
{
    int j;
    visited[i]=1;

    for(j=0;j<n;j++){
       if(!visited[j]&&G[i][j]==1){
            DFS(j);
        }
    }
}

Answer 1

您的代码有问题:

这里你在if子句中定义了另一个x，它与你在main开头定义的完全不同。

if (visited[j]==0){ // has not been visited
    int x = 0; // boolean int variable set to 0
}

而且，您还忘记在每次 DFS 之前重置 visited。