鱼C论坛

 找回密码
 立即注册
查看: 4470|回复: 3

关于DFS执行顺序的问题

[复制链接]
发表于 2015-8-6 11:15:14 | 显示全部楼层 |阅读模式
1鱼币
哪位大神告诉我图片中深度遍历 从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]
QGH25[_66$JB31H1$6B~7(4.png

最佳答案

查看完整内容

看我在你的图片上的 箭头指向(画的丑讲究看看),表示的就是 整个遍历过程中的 流程; 先由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,这里 不知 ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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已被访问,所有节点 访问结束! 递归的 一个
下行和上行的过程,把握好当前位置,和下一个位置,完成后的返回位置
001659ui3ayp8pppyobn97.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-8-6 18:51:12 | 显示全部楼层
默默路过 发表于 2015-8-6 16:31
看我在你的图片上的 箭头指向(画的丑讲究看看),表示的就是 整个遍历过程中的 流程;

先由v0开始 然后 ...

谢谢啊 今天早上想明白了 递归理解错了  不过还是谢谢你:handshake
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2015-12-23 20:42:43 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 13:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表