图的遍历（深度优先遍历）- 数据结构和算法59

图的遍历（深度优先遍历）

让编程改变世界

Change the world by program

图的遍历

树的遍历我们谈了四种方式，大家回忆一下，树因为根结点只有一个，并且所有的结点都只有一个双亲，所以不是很难理解。

但是谈到图的遍历，那就复杂多了，因为它的任一顶点都可以和其余的所有顶点相邻接，因此极有可能存在重复走过某个顶点或漏了某个顶点的遍历过程。

对于图的遍历，如果要避免以上情况，那就需要科学地设计遍历方案，通常有两种遍历次序方案：它们是深度优先遍历和广度优先遍历。

深度优先遍历

深度优先遍历(DepthFirstSearch)，也有称为深度优先搜索，简称为DFS。

它的具体思想类似于课程开头讲的找钥匙方案，无论从哪一间房间开始都可以，将房间内的墙角、床头柜、床上、床下、衣柜、电视柜等挨个寻找，做到不放过任何一个死角，当所有的抽屉、储藏柜中全部都找遍，接着再寻找下一个房间。

现在请大家一起来想办法走以下这个迷宫：

深度优先遍历

我们可以约定右手原则：在没有碰到重复顶点的情况下，分叉路口始终是向右手边走，每路过一个顶点就做一个记号。

接下来有情小甲鱼童鞋带我们走迷宫去。

迷宫走完了，所有的顶点也遍历过了，这就是深度优先遍历！

反应快的童鞋一定会感觉深度优先遍历其实就是一个递归的过程嘛~

如果再细心观察，你会发现整个遍历过程就像是一棵树的前序遍历！

深度优先遍历

看动画写代码

请观看图的深度优先遍历（邻接矩阵实现）的原理动画，结合经验自己先尝试完成代码部分。

小甲鱼将分别提供给大家邻接矩阵和邻接表的实现参考方案：点击下载

视频下载
技术, IT技术, 数据结构和算法, 遍历

                                                    风险提示及免责条款

市场有风险，投资需谨慎。本文不构成个人投资建议，也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！