如何確定特定節點是否可以找到所有其他節點？

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 :) 
}