前言
推出一个新系列,《看图轻松理解数据结构和算法》, 主要使用图片来描述常见的数据结构和算法, 轻松阅读并理解掌握. 本系列包括各种堆, 各种队列, 各种列表, 各种树, 各种图, 各种排序等等几十篇的样子.
关于图遍历
图遍历即图的遍历, 指从图中任一顶点出发, 对图中的所有顶点访问一次. 图的遍历与树的遍历相似, 但图的结构更加复杂, 比如要考虑回路的情况. 图的遍历操作是一种基本操作, 很多其他操作都建立在图遍历基础之上. 图的遍历算法主要有广度优先搜索和深度优先搜索, 这里先看广度优先搜索.
广度优先搜索
广度优先搜索 (Breadth First Search), 简称 BFS, 又称宽度优先搜索. 它是很多图的算法的原型, Dijkstra 单源最短路径算法和 Prim 最小生成树算法的思想都与 BFS 的思想类似. BFS 的时间复杂度为, 其中 为图的顶点数,为图的边数.
核心思想
选择一个初始顶点, 并将其标记为已访问;
访问 的所有未被访问过的邻接点, 并均标记为已访问;
按照 的顺序, 依次访问每一个顶点的所有未被访问过的邻接点, 并均标记为已访问;
以此类推, 直到图中所有与初始顶点 有路径相通的顶点都被访问;
如果图中的顶点还有未被访问的, 则再选出其中一个作为起始顶点, 继续执行步骤 2 到步骤 4;
遍历结束.
搜索过程
在实现过程中需要用到一个队列和一个数组, 队列用于保存所有未被检测的顶点, 而数组用于标识哪些顶点已被访问, F 表示未被访问, T 表示已被访问.
对于一个拥有 7 个顶点的无向加权图, 分别用 0-6 来表示图的每个顶点, 因为遍历与边的权重无关, 这里将权重值省略.
选择 1 作为初始顶点, 将其加入队列中, 队列头即是正在处理的顶点, 并将数组对应元素标为 T.
开始检测顶点 1 的每条边, 首先是到达顶点 0 的边,
因为顶点 0 的访问标记为 F, 说明还未被访问过, 于是将 0 加入到 BFS 队列中, 同时将访问标记改为 T.
继续检测顶点 1 的其它边, 这次是到达顶点 2 的边,
因为顶点 2 的访问标记为 F, 说明还未被访问过, 于是将 2 加入到 BFS 队列中, 同时将访问标记改为 T.
继续检测顶点 1 的其它边, 这次是到达顶点 3 的边,
因为顶点 3 的访问标记为 F, 说明还未被访问过, 于是将 3 加入到 BFS 队列中, 同时将访问标记改为 T.
顶点 1 的所有边已经被访问过了, 于是从 BFS 队列中将 1 移除, 接着处理下一个顶点, 即顶点 0.
检测顶点 0 的每条边, 首先是到达顶点 1 的边,
因为顶点 1 的访问标记为 T, 说明已经被访问过, BFS 队列和数组都不做任何更改.
继续检测顶点 0 的其它边, 这次是到达顶点 2 的边, 因为顶点 2 的访问标记为 T, 说明已经被访问过, BFS 队列和数组都不做任何更改.
顶点 0 的所有边已经被访问过了, 于是从 BFS 队列中将 0 移除, 接着处理下一个顶点, 即顶点 2.
检测顶点 2 的每条边, 首先是到达顶点 0 的边, 因为顶点 0 的访问标记为 T, 说明已经被访问过, BFS 队列和数组都不做任何更改.
继续检测顶点 2 的其它边, 这次是到达顶点 1 的边, 因为顶点 1 的访问标记为 T, 说明已经被访问过, BFS 队列和数组都不做任何更改.
继续检测顶点 2 到顶点 3 的边, 因为顶点 3 的访问标记为 T, 说明已经被访问过, BFS 队列和数组都不做任何更改.
继续检测顶点 2 到顶点 4 的边,
因为顶点 4 的访问标记为 F, 说明还未被访问过, 于是将 4 加入到 BFS 队列中, 同时将访问标记改为 T.
继续检测顶点 2 到顶点 5 的边,
因为顶点 5 的访问标记为 F, 说明还未被访问过, 于是将 5 加入到 BFS 队列中, 同时将访问标记改为 T.
顶点 2 的所有边已经被访问过了, 于是从 BFS 队列中将 2 移除, 接着处理下一个顶点, 即顶点 3.
顶点 3 相邻的所有顶点 (1,2,4,5) 的访问标记都为 T,BFS 队列和数组都不做任何更改. 继续处理顶点 4.
此时顶点 2 和顶点 3 的访问标记都为 T,BFS 队列和数组都不做任何更改. 当检测顶点 4 到顶点 6 时,
因为顶点 6 的访问标记为 F, 说明还未被访问过, 于是将 6 加入到 BFS 队列中, 同时将访问标记改为 T.
顶点 4 的所有边已经被访问过了, 于是从 BFS 队列中将 4 移除, 接着处理下一个顶点, 即顶点 5. 顶点 5 相邻的所有顶点 (2,3,6) 的访问标记都为 T,BFS 队列和数组都不做任何更改.
顶点 5 的所有边已经被访问过了, 于是从 BFS 队列中将 5 移除, 接着处理下一个顶点, 即顶点 6. 顶点 6 相邻的所有顶点 (4,5) 的访问标记都为 T,BFS 队列和数组都不做任何更改.
最终的结果如下.
来源: https://juejin.im/post/5c16fd82e51d452f8e603d97