关于DFS执行顺序的问题

bt2567

哪位大神告诉我图片中深度遍历 从v0到v5后下一个节点是什么 按程序执行怎么看都是v3啊。。。。:dizzy: 程序执行到v5跳出DFS 进入DFSTraverse执行到if( !visited[i] ) i只能等于3啊,y因为v【0 1 2 5】 已经访问过了啊。。。。我知道真确答案是v4 哪位大神解答下啊。。最好能分析下过程  彻底晕了:mad: :mad: :mad:

                               
登录/注册后可看大图

void DFS(MGraph G, int i)
{
        int j;
        
        visited[j] = TRUE;                        // 访问过的顶点设置为TRUE[i]
        printf("%c ", G.vexs);        // 打印顶点
        for( j=0; j < G.numVertexes; j++ )[/i][i]
        {[/i][i][i]
                if( G.arc[i][j]==1 && !visited[j] )
                {
                        DFS(G, j);                        // 对为访问的邻接顶点递归调用
                }
        }
}

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

默默路过

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

先由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 16:31
看我在你的图片上的 箭头指向（画的丑讲究看看），表示的就是 整个遍历过程中的 流程；

先由v0开始 然后 ...

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