使用鄰接矩陣的深度優先搜索

任何人都可以解釋使用鄰接矩陣進行深度優先搜索的算法嗎？我知道使用遞歸進行深度優先搜索的算法，我嘗試使用Adjacency矩陣來實現它，但它不是很成功。使用鄰接矩陣的深度優先搜索

我有什麼到目前爲止

dfs(G,i){ 

    mark i as visited; 

    for(traverse through the edges of i vertex){ 

    if(vertex of edge is unseen){ 

     DFS(G,newVerted) 
    } 
    } 

}

來源

2012-08-03 Dude

什麼錯？理論上你的僞代碼看起來很好（除了BFS部分:)。如果您可以使用鄰接列表來執行DFS，那麼使用矩陣進行操作應該只是循環遍歷該矩陣的行並查看位的設置位置以及未訪問的頂點 – dfb 2012-08-03 22:04:47

您是否瞭解深度優先搜索是？你知道一個鄰接矩陣是什麼嗎？ – 2012-08-03 22:10:15

我認爲這是最簡單的，只是像迷宮，你總是向左走。如果您來自n節點，請按遞增順序循環訪問下一個節點。

我只是不知道你怎麼知道你來了：D但很酷的事情是，你不需要額外的空間和標記。

EDIT
例如

Am進行然後

......1 
..1.... 
.1..11. 
1.....1 
..1...1 
..1.... 
1..11..

所以從5訂購開始是 3 6 3 2 3 5 7 1 7 4 7 5 3＃和因爲你從5 - > 3

正如我所說，如果你在節點上，你去下一個節點基於n你是從哪裏來的。您將要訪問的下一個節點是來自Prevous節點的下一個數字（不是當前節點）。

來源

2012-08-03 22:05:13

我想你可以通過維護堆棧和訪問列表，並使用while循環：訪問是一個bool []，初始化爲在所有位置保持false，並且我假設調用G [node，neighbor]以某種方式返回一個布爾值，告訴節點是否存在從邊到邊的邊。（隱比較1或簡單地使鄰接矩陣保持布爾）
堆棧握着你的節點的索引：

dfs(G,i){ 
    Initialize Stack 
    Current = i 
    PossibleEdge = 0 
    Visited[Current] = true //You have visited the starting node 
    Do { 
     While (PossibleEdge < count) { 
      if (G[Current,PossibleEdge] && NOT Visited[PossibleEdge]){ 
       Stack.Push(Current)  //Save state 
       Current = PossibleEdge //Continue with the child node 
       Visited[Current] = true 
       PossibleEdge = -1  //So that it will be incremented to 0 
      } 
      PossibleEdge++ 
     } 
     PossibleEdge = Current   //Continue to next row of "parent node" 
     Current = Stack.Pop()   //Get parent node back 
    } While (Stack contains nodes) 
}

我敢肯定，它可以優化（而當看到我累得要死，有可能是一些邏輯錯誤），但如果基本過程有意義，那就是一個開始！
編輯：澄清，並添加這個提示：遞歸是可能更容易;）

來源

2012-08-03 22:49:47 olagjo

你錯過了在功能打印dfs(G,i)

的代碼如下

dfs(G,i){ 
int j; 
printf("%d ",i); 
visited[i]=1; 
for(j=0;j<n;j++){ 
    if(visited[j]==0&&G[i][j]==1) 
     dfs(G,j); 
}

這裏我們使用變量n作爲Graph.G中的頂點數是成本鄰接矩陣。

來源

2015-06-05 17:06:02

void DFS(int i) 
    { 
     int j; 
     printf("\n%d",i); 
     visited[i]=1; 
     for(j=0;j<n;j++) 
      if(!visited[j]&&G[i][j]==1) 
       DFS(j); 
    }

哪裏n是沒有頂點和G是圖形和G[i][j]表示頂點i連接到頂點j

來源

2015-06-22 13:24:00

使用鄰接矩陣的深度優先搜索

回答

相關問題