当前位置:鱼C工作室 >数据结构和算法 > 查看文章

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

图的遍历(深度优先遍历)

 

让编程改变世界

Change the world by program


 

图的遍历

 

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

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

 

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

 

深度优先遍历

 

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

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

 

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

深度优先遍历

深度优先遍历

 

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

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

 

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

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

 

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

深度优先遍历

深度优先遍历

 

看动画写代码

 

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

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


为您推荐

报歉!评论已关闭.