图——搜索算法及其应用(二)

type

status

date

slug

summary

1. 概述

为什么我们要搜索一个图，或者弄清楚一个图是否是否包含从 A 点到 B 点的路径？原因有很多，我们简单罗列几个：

检查连通性。在交通道路网络或者计算机网络中，一项重要的检查就是你是否可以从任意一点到达其他任意一点。也就是说对于网络中任意两点 A 和 B，都应该存在一条路径。

最短路径。很多问题都可以归结为最短路径的计算，其中"短"的定义取决于具体应用，比如：使得驾驶时间”最短”，或使得旅行的费用“最小”。广度优先搜索非常适用于计算最短路径。

规划。图中的路径不必有具体的物理含义。抽象一点说，路径是从一个状态到另一个状态的决策序列（状态对应图中的点）。图搜索算法则是计算是否存在一条从初始状态到达目标状态的路径（规划）。

连接分量。我们还将看到如何利用图的搜索算法计算图的连通分量。定义和计算无向图的连通分量相对简单。对于有向图图来说，即使是”连通分量“的定义都有些微妙。连通分量对于理解图的整体结构非常重要。

1.1 图的搜索

图搜索算法是用来解决以下这个问题的:

📌

问题：图的搜索 输入：一个无向图或者有向图，以及一个起始顶点。目标：找出图中从可达的所有顶点。

顶点可达，意思是：在图中存在一条从到的路径。

比如，下面两幅图中：

图（a）中，从可达的顶点有。图（b）中，从可达的顶点有，注意顶点是不可达的，因为不存在一条从到的有向路径。

💡

伪代码：通用搜索输入：图和起始顶点。 完成状态：当且仅当一个顶点被标记为已探索，它才是从可达的。 ——————————————————————————————————————————

把标记为已探索，所有其他顶点均标记为未探索 while 存在一条边且已探索、未探索 do 选择一条这样的边 //不够明确把标记为已探索

这个算法在本质上对于有向图和无向图是相同的。如果是有向图，那么在 while 循环的一次迭代中所选择的边应该是一条从已探索顶点到未探索顶点的有向边。

通用搜索算法在每次迭代的时候，会在“边界”上选择一条边，该边的一个顶点是已探索的，另一个顶点是未探索的。

这样的边可能有多条，为了使算法更为明确，我们需要使用一种方法在这些边中选择某一条。一般我们有两种策略：广度优先搜索和深度优先搜索。它们都是搜索图的优秀算法，分别应用于不同的场景。

2. 广度优先搜索和最短路径

现在，我们把注意力集中在第一种特定的图搜索算法——广度优先搜索（Breadth-First Search, BFS）。

BFS 是以分层的方式搜索图的顶点的。只包含起始顶点s；包含的顶点是s的邻居，也就是和s的距离为 1 的顶点；以此类推，中的顶点是中某个顶点的邻居，并且不属于前面的任何一层。并且 BFS 是按顺序依次访问各层中的顶点的。

⏰

小测验 一个具有个顶点的无向图，它的最小层数和最大层数分别是多少？ (a) 1 和 n-1 (b) 2 和 n-1 (c) 1 和 n (d) 2 和 n

2.1 BFS的实现

想在线性时间复杂度内实现 BFS，我们需要借助队列。BFS 使用队列来记录下一步要访问的顶点。它的伪代码如下：

📌

伪代码：BFS 输入：邻接表表示的图和起始顶点。 完成状态：当且仅当一个顶点被标记为已探索，它才是从可达的。 —————————————————————————————————————————— 把标记为已探索，所有其他顶点标记为未探索。 Q := 队列，并将起始顶点入队列 while Q 不为空 do 从 Q 的队头删除一个顶点，称之为 for 邻接列表中的每条边 do if 为未探索 then 把标记为已探索把添加到 Q 的尾部

它的C++实现如下：

BFS 的独到之处在于，在 BFS 算法中额外增加几行代码，就能高效地计算最短路径距离问题。

2.2 最短路径

在图 G 中，我们使用表示从到的距离（从到最短路径的长度），如果不存在从到的路径，则。

❓

问题：最短路径（边的长度） 输入：无向图或有向图，起始顶点。输出：每个顶点的。

计算最短路径，我们只需要在基本的 BFS 中添加了两行额外的代码。第一行代码进行初始化，初始化为，其他顶点则初始化为（即无法从到达）。第二行代码是在顶点初次被发现时执行的，它计算的最短路径，也就是在顶点的基础上加一（触发了的发现）。伪代码如下：

📌

伪代码：最短路径（边的长度）

输入：邻接列表表示的图和起始顶点。 完成状态：对于每个顶点，的值等于最短路径长度。 —————————————————————————————————————————— 把标记为已探索，所有其他顶点标记为未探索对于每一个顶点，队列，将顶点入队列 while 不为空 do 从的对头出队列一个顶点，称之为 for 邻接列表中的每一条边 do if 为未探索 then 把标记为已探索把入队列

(课后作业：用 C++ 实现最短路径)

3. 计算无向图的连通分量

在本节中，总是表示无向图。有向图的连通性问题，比较复杂，我们不讲。

3.1 连通分量

什么是连通分量呢？直观地讲，无向图的连通分量，就是无向图中相互连接的“片段”。更正式的定义是，连通分量是顶点的一个最大子集，满足：中的任一顶点都存在通向中其他任何顶点的路径。例如，下图有三个连通分量，分别是、和。

这一节的主题就是利用 BFS，在线性时间复杂度内，计算无向图的连通分量。

❓

问题：无向图的连通分量 输入：无向图。目标：确认的连通分量。

计算无向图的连通分量可以很方便地简化为 BFS (或 DFS)。它的思路是使用一个外层循环对所有顶点进行一次遍历，当遇到一个此前未探索的顶点时，则以为起始顶点，调用 BFS。这个外层循环保证了每个顶点都会被遍历一次。

📌

伪代码：无向图的连通分量 (UCC) 输入：邻接列表表示的无向图，。 完成状态：对于每对，当且仅当和位于同一个连通分量时，。 —————————————————————————————————————————— 把所有顶点标记为未探索 numCC := 0 for i := 1 to n do // 遍历所有的顶点 if i 未为探索 then numCC := numCC + 1 // 新的连通分量 // 以 i 为起始顶点，调用 BFS Q := 队列，将顶点 i 入队列 while Q 非空 do 从 Q 的队头出队列一个顶点，称之为 v cc(v) := numCC for v 邻接列表中的每条边 (v,w) do if w 为未探索 then 把 w 标记为已探索把 w 添加到 Q 的队尾

它的 C++ 实现如下：

3.2 应用场景

为什么我们会对计算连通分量感兴趣呢？

检测网络故障 连通分量的一个显而易见的应用是检查一个网络(例如道路交通网、或互联网)是否断开连接。

数据可视化 连通分量的另一个应用是图的可视化。如果我们要绘制一个图或者获取该图的某种可视化形式，那么很可能需要独立地显示它的不同连通分量。

聚类假设我们有一个对象集合，“相似的”对象之间有一条边。那么连通分量中包含的就是所有“相似的”对象，达到了聚类的效果。

4. 深度优先搜索

为什么我们还需要学习另一种图搜索算法？毕竟，BFS 看起来非常棒 —— 它能在线性时间内找到从起始顶点出发可到达的所有顶点，还能在线性时间复杂度内计算最短路径和无向图的连通分量。

但有些应用 BFS 处理起来会比较棘手，比如有向无环图（directed acyclic graph, DAG）顶点的拓扑排序，以及有向图的强连通分量。而深度优先搜索（Depth-First Search, DFS）可以很好地处理这些问题。

4.1 示例

如果说广度优先搜索是一种谨慎、试探性的探索策略；那么深度优先搜索则是一种激进的探索策略，它总是从最近发现的顶点开始探索，只有在必要时才回溯（就像探索迷宫一样）。其中是起始顶点。

4.2 DFS 的伪代码

📌

伪代码：DFS 输入：邻接列表表示的图和起始顶点。 完成状态：一个顶点当且仅当它被标记为“已探索”时，才是从可达的。 —————————————————————————————————————————— 将 s 标记为已探索，所有其它顶点标记为未探索 for s 邻接列表中的每条边 (s,v) do if v 为未探索 then DFS(G,v)

它的 C++ 实现如下：

5. 拓扑排序

5.1 什么是拓扑排序

深度优先搜索非常适合计算有向无环图的拓扑排序。你可能会问：“什么是拓扑排序？”，“它又有什么作用？”。

假设你有一堆任务要完成，而且任务之间存在优先级约束；也就是说，某个任务依赖于其它任务，在其它任务未完成之前，我们是不能开始这个任务的。比如，大学里的课程。拓扑排序就是对所有任务进行排序，使所有优先级约束都得到遵守。

📌

拓扑排序 假设是个有向图。的拓扑排序就是为每个顶点分配一个不同的数字，使得：对于每条有向边，均满足。

函数有效地对顶点进行了排序，函数值小的元素在前面，函数值大的元素在后面。

⏰

下面的有向无环图中，有多少种不同的拓扑排序？使用进行编号。

a) 0

b) 1

c) 2

d) 3

我们可以将拓扑排序可视化。将所有顶点按照赋值给它们的值从左到右排序。如下图所示，所有的边都是从左指向右的。

5.2 什么样的图存在拓扑排序

是不是每个图都存在拓扑顺序呢?不是。考虑一个有向环组成的图。无论我们选择什么样的顶点顺序，沿着这个环的边向前访问总是可以到达起始顶点。

不管按什么顺序访问，必然会存在一条反向的边，因此有向环不存在拓扑排序。一个更普遍的结论是：如果一个图包含有向环，那么这个图不存在拓扑排序。

令人愉快的是，有向环是拓扑顺序唯一的障碍。没有任何有向环的有向图称为有向无环图，简称 DAG。

📌

定理：每个 DAG 都具有拓扑排序 每个有向无环图至少具有 1 个拓扑排序。

5.3 如何计算拓扑排序

所以，我们就有接下来的这个问题：如何计算有向无环图的拓扑排序。

❓

问题：拓扑排序 输入：有向无环图。输出：所有顶点的一个拓扑排序。

伪代码如下：

📌

伪代码：Topo-Sort 输入：邻接列表表示的有向无环图。 完成状态：顶点的 f 值构成了的一个拓扑排序。 —————————————————————————————————————————— 把所有顶点标记为未探索 curLabel := |V| // 记录顺序 for 每个 do if 为未探索 then Topo-DFS(G,v)

📌

伪代码：Topo-DFS 输入：用邻接列表表示的有向无环图和顶点。 完成状态：每个可以从到达的顶点被标记为“已探索”，并分配了一个值。 —————————————————————————————————————————— 把 s 标记为已探索 for s 外向邻接列表中的每条边 (s,v) do if v 为未探索 then Topo-DFS(G, v) f(s) := curLabel // 为 s 分配 f 值 curLabel := curLabel - 1 // 从右向左排序

C++实现如下：

归纳总结

参考文献

一些引用

引用文章

💡

欢迎您在底部评论区留言，我们一起交流学习~