3

谁能解释使用邻接矩阵进行深度优先搜索的算法？我知道使用递归的深度优先搜索算法，我尝试使用邻接矩阵来实现它，但它不是很成功。

到目前为止我所拥有的是

 dfs(G,i){

  mark i as visited;

  for(traverse through the edges of i vertex){

     if(vertex of edge is unseen){

       DFS(G,newVerted)
     }
   }

}
4

4 回答 4

7 
    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-22T13:24:00.787 回答
4

您错过了打印功能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-05T17:06:02.337 回答
0

我认为最简单的方法是，就像在迷宫中你总是向左走。如果您来自 n 个节点，则按递增顺序循环进入下一个节点。

我只是不知道你怎么知道你来了 :D 但很酷的是你不需要额外的空间和标记。

编辑
示例

    5
   / \
  7   3
 /\   /\
4  1 6  2

那时是

......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

正如我所说，如果你在节点上，你会根据你来自的节点继续下一个节点。您要访问的下一个节点是前一个节点（不是您从当前节点）的下一个数字。

于 2012-08-03T22:05:13.747 回答
0

我想你可以通过维护一个堆栈和一个访问列表并使用一个while循环来做到这一点：Visited is a bool[]，初始化为在所有位置都保持假，我假设调用 G[node,neighbour]以某种方式返回一个布尔值，说明从节点到邻居是否存在边。（隐式比较 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-03T22:49:47.423 回答