圖的連接

Question

int dfs(int graph[MAXNODES][MAXNODES],int visited[],int start) { 
int stack[MAXNODES]; 
    int top=-1,i; 
    visited[start]=1; 
    stack[++top]=start; 
    while(top!=-1) 
    { 
    start=stack[top]; 
     for(i=0;i<MAXNODES;i++) { 
    if(graph[start][i]&&visited[i]==0) { 
       stack[++top]=i; 
       printf("%d-",i); 
       visited[i]=1; 
       break; 
      } 
     } 
    if(i==MAXNODES) 
      top--; 
    } 
    return 0; 
} 

上面的代碼實現了作爲鄰接矩陣存儲的圖上的dfs，我請求一個建議，我應該怎麼做才能知道生成的圖是否連接。

Answer 1

查看我的answer有關強連通組件的更早問題。

你的dfs的寫入效率也很低，因爲你重複掃描i = 0;你的堆棧應該記住你離開的地方並從那裏繼續。遞歸更自然，但如果你有有限的調用堆棧大小，那麼顯式堆棧是最好的（僅適用於巨大的樹）。

這是一個遞歸dfs。如果你不感興趣的存儲DFS樹，你可以存儲1前任[]，而不是節點你達到它）：

const unsigned MAXNODES=100; 

/* predecessor must be 0-initialized by the caller; nodes graph[n] that are 
reached from start will have predecessor[n]=p+1, where graph[pred] is the 
predecessor via which n was reached from graph[start]. 
predecessor[start]=MAXNODES+1 (this is the root of the tree; there is NO 
predecessor, but instead of 0, I put a positive value to show that it's 
reached). 

graph[a][b] is true iff there is a directed arc from a->b 

*/ 

void dfs(bool graph[MAXNODES][MAXNODES],unsigned predecessor[] 
     ,unsigned start,unsigned pred=MAXNODES) 
{ 
    if (predecessor[start]) return; 
    predecessor[start]=pred+1; 
    for (unsigned i=0;i<MAXNODES;++i) 
     if (graph[start][i]) 
      dfs(graph,predecessor,i,start); 
} 

這裏有圖案的上述非遞歸DFS，但使用pred和i相同的堆棧變量（一般你就必須爲每一個局部變量和參數堆棧變量，可以在你的遞歸改變）：

void dfs_iter(bool graph[MAXNODES][MAXNODES],unsigned predecessor[] 
       ,unsigned start) 
{ 
    unsigned stack[MAXNODES]; // node indices 
    unsigned n,pred; 
    int top=0; 
    stack[top]=start; 
    for(;;) { 
    recurse: 
     // invariant: stack[top] is the next (maybe reached) node 
     n=stack[top]; 
     if (!predecessor[n]) { // not started yet 
      pred=top>0?stack[top-1]:MAXNODES; 
      //show(n,pred); 
      predecessor[n]=pred+1; 
      // the first thing we can reach from n 
      for (unsigned i=0;i<MAXNODES;++i) 
       if (graph[n][i] && !predecessor[i]) { 
        stack[++top]=i; goto recurse; // push 
       } 
     } 
     if (top>0) { 
      pred=stack[top-1]; 
      // the next thing we can reach from pred after n 
      for (unsigned i=n+1;i<MAXNODES;++i) 
       if (graph[pred][i]) { 
        stack[top]=i; goto recurse; // replace top 
       } 
      --top; 
     } else 
      return; 
    } 
} 

這可能沒有轉到結構化（它只是一個名字繼續到最外面的循環），但在我看來沒有更真實的清晰度。

無論如何，遞歸調用要簡單得多。有Tarjan's strongly connected components algorithm的遞歸僞代碼，你可以直接轉錄。如果您需要幫助使其成爲非遞歸（顯式堆棧），請詢問。

Answer 2

您需要存儲從一個節點行進到下一個節點所產生的邊緣。然後，您可以驗證圖中的所有節點是通過邊連接的。

Answer 3

運行Dijkstra算法。如果最後你的隊列是空的，並且一些頂點沒有着色，那麼你的圖形沒有連接。這是線性時間的保證，dfs方法是二次方的最差情況分析。