首页 > 笔记 > 图的遍历

图的遍历

本文介绍的算导上的图的遍历。。。很基础

bfs

广搜就是广度优先搜索,根据名字可以知道,是通过广度来遍历图,也就是层次遍历。

在这里以及下面的DFS(深搜),都用到了颜色WHITE,GRAY,BLACK,不过作用不同,具体分别再分析。

在BFS中,WHITE,GRAY,BLACK这三色是用来记录一个点是否被搜到,以及是否它的邻接点都是灰色。

 

images

数据

8
0 1 0 0 0 0 0 1
1 0 0 0 0 0 1 0
0 0 0 1 0 1 1 0
0 0 1 0 1 1 0 0
0 0 0 1 0 1 1 0
0 0 1 1 1 0 0 0
0 1 1 0 1 0 0 0
1 0 0 0 0 0 0 0

dfs

在DFS中,仍然用到了WHITE, GRAY,BLACK,但是它们的用处和BFS有些不同,这里他们是用来表示时间戳,因为DFS会有回溯,所以也就有第一次和第二次搜到。

images

数据

6
0 1 0 0 0 1
0 0 0 0 1 0
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 0 0 1
0 1 0 0 0 0

全部实现的(来自网络

结果

这里写图片描述


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×