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

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

一些错误代码：

这里，你确定另一x内if clause，这是从你的main开始定义的一个完全不同的。

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

而且，你也忘了每DFS之前重置visited。

Answer 2

正如其他答案所说，你的代码是错误的。您不设置visited[]的值（并且应该在每个循环中重置它们）。您返回main()中的节点号码，这可能是无用的。如果你设置了x = 0;应该离开循环（用break）：不需要检查其他值。如果i==j（取决于您的图形编码），您不应该检查G [i] [j]。

但你为什么要这么复杂的代码？如果我理解得很清楚，你只需要寻找一个连接到其他节点的节点。因此visited[]不是有用的。节点i连接到所有其他G[i][j]==0如果没有j。它可能是：

// returns true (1) if i connected, false (0) else 
int DFS(int i) { 
    int j; 
    for(j=0; j<n; j++) { 
    if ((j != i) && (G[i][j] == 0)) { 
     return 0; // we know it is not "complete" 
    } 
    } 
    return 1; // not false -> true :) 
}