bt2567 发表于 2015-8-6 11:15:14

关于DFS执行顺序的问题

哪位大神告诉我图片中深度遍历 从v0到v5后下一个节点是什么 按程序执行怎么看都是v3啊。。。。:dizzy: 程序执行到v5跳出DFS 进入DFSTraverse执行到if( !visited ) i只能等于3啊,y因为v【0 1 2 5】 已经访问过了啊。。。。我知道真确答案是v4 哪位大神解答下啊。。最好能分析下过程彻底晕了:mad: :mad: :mad: http://bbs.fishc.com/forum.php?mod=image&aid=37926&size=300x300&key=8687d89ea97e23f0&nocache=yes&type=fixnone
void DFS(MGraph G, int i)
{
      int j;
      
      visited = TRUE;                        // 访问过的顶点设置为TRUE
      printf("%c ", G.vexs);      // 打印顶点
      for( j=0; j < G.numVertexes; j++ )
      {
                if( G.arc==1 && !visited )
                {
                        DFS(G, j);                        // 对为访问的邻接顶点递归调用
                }
      }
}

// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G)
{
      int i;
      
      for( i=0; i < G.numVertexes; i++ )
      {
                visited = FALSE;                // 初始化所有顶点状态都是未访问过状态
      }
      
      for( i=0; i < G.numVertexes; i++ )
      {
                if( !visited )                // 若是连通图，只会执行一次
                {
                        DFS(G, i);
                }
      }
}

默默路过 发表于 2015-8-6 11:15:15

看我在你的图片上的 箭头指向（画的丑讲究看看），表示的就是 整个遍历过程中的 流程；

先由v0开始 然后是 一直到v5 这个时候 代码因为 5 没有后续连接的图，那么对于5的递归 DFS(G, 5) 函数执行完成
返回到DFS（G，2）,而2 只有5相连，函数执行结束，此时返回到 DFS(G,1)，在1里面2被访问完成，接下来自然是
访问4，直接进入DFS(G,4)，此函数中有0 和 6 相连，因为0已访问，固直接访问6 DFS(G,6) 函数6中有3和7，这里
不知道你的优先级是怎么设定的我 就先访问了7，然后 返回到6 再去访问3， 然后3发现0被访问直接返回到6，这样
6访问结束 返回到4,4访问结束 返回到1,1访问结束 返回到 0,0 发现3已被访问，所有节点 访问结束！ 递归的 一个
下行和上行的过程，把握好当前位置，和下一个位置，完成后的返回位置！

bt2567 发表于 2015-8-6 18:51:12

默默路过 发表于 2015-8-6 16:31
看我在你的图片上的 箭头指向（画的丑讲究看看），表示的就是 整个遍历过程中的 流程；

先由v0开始 然后 ...

谢谢啊 今天早上想明白了 递归理解错了不过还是谢谢你:handshake

莫欺少年穷 发表于 2015-12-23 20:42:43

页: [1]
查看完整版本: 关于DFS执行顺序的问题