钻头
PDF钻头
高效图搜索
完成时停止。
特伦斯·凯利
欢迎来到 钻头，这是一个关于编程的新专栏，旨在扩展您的工具箱并帮助您编写更好的软件。 大部分内容将包括位和钻：示例代码和练习，以磨练您的技能。
当我写下这些文字时，大部分人类正处于 COVID-19 大流行封锁之下； 全球范围内禁止非必要活动。 非常应景的是，《 钻头 》的试播集借鉴了时代精神，即消除不必要的工作的原则。
图搜索再探
图为异常广泛的实际系统（从电子电路到社交网络）提供了一种通用的、统一的抽象。 图搜索是分析图及其代表的现实世界系统的基础。 标准图搜索算法是否还有改进空间？
本专栏深入探讨了 BFS（广度优先搜索），它本身很有用，并且是更复杂分析的构建块。9 在快速回顾经典的 BFS 算法（如图 1 所示）之后，我将展示如何使用一种技术来提高其效率，该技术也可以类似地改进其他图分析。 BFS 可以处理有向图，但为了简洁起见，我们将仅考虑无向图。 在另行通知之前，我们将注意力限制在连通图上，其中每对顶点都通过某个边序列连接。
BFS 的输入是一个无权图，其顶点编号为 1 到 V。 每个顶点 u 的相邻顶点（“邻居”）通过 (u,v) 形式的无向边与其连接。 E 表示边的数量，s 表示搜索开始的源顶点。
BFS 计算每个顶点 v 的两个相关输出4：从源的距离（即，s 和 v 之间最短路径上的边数），以及从 v 的邻居中选择的父顶点。 移动到 v 的父顶点、祖父顶点、曾祖父顶点等，可以追踪到 s 的最短路径； 回溯会产生从 s 到 v 的最短路径。 所有顶点的距离和父字段最初都为零。 没有单独的字段来指示 BFS 已经找到一个顶点，因为零不是有效的顶点 ID； 已发现的顶点是那些分配了非零父顶点的顶点。 在连通图上，从任何源开始的 BFS 都会找到所有顶点。
BFS 的中心数据结构是一个 FIFO（先进先出）队列，其中包含已发现顶点的 ID，这些顶点的邻居等待检查。 最初，队列为空。
BFS 首先初始化源顶点 s 并将其入队，源顶点 s 到自身的距离为零，并被定义为其自身的父顶点。 一个外循环（图 1 的第 4 行）重复将顶点 u 出队，并在一个内循环（第 6 行）中检查其邻居。 如果尚未找到邻居 v，则将其距离设置为比 u 的距离大 1，将其父字段设置为 u，并且 v 进入队列。 当第 4 行发现队列为空时，经典 BFS 终止。
三十六计，走为上计。
— 中国军事格言
高效搜索
程序员通常希望使软件更快。 不幸的是，直接提高速度的机制通常会降低效率，就像喷气发动机的加力燃烧室提高了 MPH，但降低了 MPG 一样。 相比之下，消除浪费的努力通常也会使软件更快，因此我们应该首先努力实现提高效率的双赢。 BFS 能否以更少的工作量计算出相同的输出？
考虑图 1 中的终止测试。 第 4 行的 while 循环在最后一个顶点从队列中出来后退出，它的邻居已被检查，并且没有邻居被入队，从而使队列为空。 这是输出达到其最终状态的时刻吗（即，每个顶点都被分配了距离和父顶点的时刻）？ 显然不是：在为最后一个顶点分配距离和父顶点之后，经典 BFS 将该顶点插入队列， 从而破坏了终止测试。
为了理解经典 BFS 的效率有多低，请将其应用于完全图，其中存在所有 V ✕ (V - 1)/2 个可能的边，并且每个顶点都与每个其他顶点相邻。 在第一次遍历 while 循环时，第 6 行的 for 循环迭代源的所有邻居（即，图中的所有其他顶点），并为其距离和父字段分配最终值。 此时，计算的整个输出已达到其最终状态。 可惜的是，源的所有 V - 1 个邻居都进入队列； 当它们出队时，它们的所有邻居都会被检查。 在完全图上，经典 BFS 在执行与 V 成比例的工作后完成其输出，然后盲目地匆忙通过队列中剩余的忙碌工作，最终执行与 V2 成比例的总工作量。
幸运的是，对经典 BFS 的简洁修改消除了所有浪费的努力。 图 2 显示了增强功能 E-BFS（高效 BFS）。 变量 f 计数具有最终输出字段的顶点。 第 3 行将 f 初始化为 1，表示源顶点。 在设置新发现顶点的输出字段后，计数器递增，并在第 11 行与 V 进行比较。 当 f 等于 V 时，所有输出都已达到静止状态，并且可以安全地终止，而与队列中剩余的内容无关； 第 12 行通过直接跳转到第 17 行来跳出两个循环。 实现会在读取输入图时学习 V，并且如果图是连通的，则 f 最终必须等于 V，因此第 11 行的测试最终会成功。
值得注意的是，图 2 中改进的 BFS 似乎既不广为人知，也不被广泛使用。 经典 BFS 单独出现在顶级计算机科学教科书中4,11、关于图和网络的高级文本中1,9、学生的 Web 资源中6,12、专业程序员的书籍中7,10、工业级图软件中3，以及无数的研究论文中。
评估
经典 BFS 的渐近分析非常简单。 在图 1 中，第 4 行的外 while 循环每个顶点迭代一次，第 6 行的内 for 循环每条边迭代两次（每个端点一次）。 因此，无论输入图的具体情况如何，经典 BFS 在具有 V 个顶点和 E 条边的连通图上的运行时间都严格地以下限和上限 V + E 为界。 在渐近分析的术语中，经典 BFS 的运行时间既是 Ω(V + E) 又是 O(V + E)； 等效地，运行时间为 𝝝(V + E)。
相比之下，对于 E-BFS，输入图的具体情况确实会影响渐近运行时间：下界更好。 如图 2 所示，第 7 行的内 for 循环对于源顶点的每个邻居迭代一次，源顶点最多可能有 V - 1 个邻居，因此 E-BFS 的运行时间以下限 V 为界。 E-BFS 在完全图上达到此下限，因为它在检查源的每个邻居后终止，因此运行时间为 Ω(V)。 E-BFS 具有与经典 BFS 相同的渐近上限运行时间—O(V + E)—因为某些输入迫使 E-BFS 检查每条边（例如，将一棵小树附加到大型完全图，并在后者上选择源）。
渐近运行时间差异在实践中重要吗？ 为了找出答案，我实现了 BFS 的两个变体，并进行了两个实验：第一个实验使用完全图，这突出了经典 BFS 的最坏情况； 第二个实验使用稀疏图，其中仅包含可能边的一小部分，这在实际应用中更常见。
图 3a 显示了不同大小的完全图的经典 BFS 平均运行时间与 E-BFS 平均运行时间的比率。 平均值取自来自不同源的 21 次搜索； 绘制中位数而不是平均值会产生类似的图。 经典 BFS 执行与 V2 成比例的工作，而 E-BFS 执行与 V 成比例的工作，因此运行时间比率与 V 成比例地增加。 对于具有 2,000 个顶点（因此有 1,999,000 条边）的完全图，E-BFS 比经典 BFS 快 9,400 多倍。 对于 V =10,000（因此 E = 49,995,000），E-BFS 的速度提高了近 73,000 倍。
稀疏图，其中 E 远小于 V ✕ (V - 1)/2，在实践中经常出现。 图 3b 显示了稀疏随机连通图的经典/E-BFS 运行时间比率。 每个图都有 225 条边（大约 3350 万条）； 顶点的数量以及它们的平均度数各不相同。 前 V - 1 条边将所有顶点连接到单个连通分量：范围 [2..V] 中的每个顶点 ID v 都有一个邻居 ID u，该邻居 ID u 以均匀概率从 [1..(v - 1)] 中抽取。 后续边是 (u,v) 对，其中两个 ID 都以均匀概率从 [1..V] 中选择，并且 u ≠ v。 图 3b 表明，对于平均度数非常低的图（实际上是树的稀疏图），E-BFS 比经典 BFS 稍慢。 对于此类图，经典 BFS 效率相当高，并且递增和比较 E-BFS 计数器 f 的额外开销使搜索速度比经典 BFS 慢 1% 到 4%。 但是，随着平均度数增加到大约 16 以上，E-BFS 开始获胜； 当平均度数为 512 时，它的速度快 40 倍。
理论和实验都指向相同的结论：高效 BFS 永远不会比经典 BFS 慢很多，有时它会快得多。 E-BFS 的基本原则（在输出最终确定时停止）只是常识。 实现 E-BFS 只需向经典 BFS 添加几行简单的代码。 鉴于这些优势，E-BFS 应该比迄今为止受到更多的关注。 今后，它应被视为标准基线 BFS 算法。
跳过不必要的工作
修复终止测试
完成时停止
更进一步
E-BFS 可以推广到连通图之外。 如果图不连通，则从任何源开始的 BFS 将找到少于 V 个顶点，因此图 2 第 11 行的比较将永远不会成功。 幸运的是，通过将每个顶点与其连通分量的大小相关联，并在计数器 f 等于包含源的分量的大小时终止，可以很容易地恢复 E-BFS 的功效。 您可以通过在每个分量中运行一次 BFS 来获得分量大小。 在实践中，输入图通常以边列表的形式给出，并且 BFS 实现使用邻接表表示图。 每个分量运行一次经典 BFS 的成本在常数因子内与从边列表构建邻接表表示的成本相同。 如果您必须在同一图上从许多源顶点运行 BFS，则预先计算分量大小的前期成本稍后可能会通过 E-BFS 节省来弥补。
作为 E-BFS 如何利用分量大小的具体示例，请考虑将其应用于表示疾病传播可能路径的社交接触图。 如果疾病检测用品短缺，则必须为最有可能广泛传播感染的人保留它们（例如，因为他们有很多接触者，或者因为他们的接触者有很多接触者）。 接近中心性是一种图指标，用于识别此类个体。9 计算接近中心性需要从每个顶点运行 BFS。 如果给定的社交接触图不连通，则 E-BFS 不会简化每个连通分量中的第一次搜索。 然而，将分量的大小与所有顶点相关联作为第一次搜索的额外好处是廉价且容易的，因此分量中的后续搜索受益于 E-BFS。
最后，BFS 并不是唯一可以从图 2 技术中受益的算法。 我在一个串行 MIS（最大独立集）程序中使用了它，它显着提高了效率和速度。 计算与 BFS 相同输出（每个顶点的距离和父字段）的 DFS（深度优先搜索）程序可以像 BFS 一样有利地使用该技术。 然而，DFS 通常用于计算额外的输出，例如，对图的所有边进行分类，这本身就需要与 E 成比例的工作； 经典 DFS 对于此目的来说效率相当高。
位
我的实验中使用的所有源代码都可以在 https://queue.org.cn/downloads/2020/Drill_Bits_01_sample_code.tar.gz 找到。 两个 C 程序生成连通无向图：一个生成完全图，另一个生成稀疏随机图。 BFS 程序也用 C 实现，默认运行经典 BFS； 编译时选项启用 E-BFS。 一个 shell 脚本显示了我如何编译 C 程序并运行实验； 第二个脚本对运行脚本的输出进行后处理，以获得简洁的摘要。
演练
实践经验是建立直觉的最好方法。 以下是一些练习，难度和目标由低到高，从小调整到大型项目
1. 示例 BFS 程序中的 FIFO 队列是一个数组 Q，通过整数下标访问，如 Q[i] 中所示。 指针更快吗？ 更清晰吗？
2. 测量经典 BFS 以量化输出最终确定后执行的工作。 队列中还剩下多少个顶点？ 它们有多少个邻居？
3. 如图 2 所示，goto 的使用可能会引发过敏反应。5 通过更改两个循环来实现没有 goto 的 E-BFS。 或者，goto 更长的长度来冒犯纯粹主义者，方法是通过 longjmp() 或 throw 跳出嵌套循环。
4. 在不同类型的图（例如，合成小世界图9 或真实世界图）上运行实验。 E-BFS 在这些图上是否优于经典 BFS？
5. 尝试不同的图表示（例如，邻接矩阵或压缩稀疏行）。 与邻接表相比，性能是否有所提高？ 如果是这样，值得付出努力吗？
6. 比较串行经典 BFS、串行 E-BFS 和横向扩展分布式 BFS 实现的性能。 您的结果是否与过去对可扩展数据分析2 和可扩展图分析8 的评估一致？
7. E-BFS 在有向图上何时有效？ 什么预处理有帮助？
8. 使用 E-BFS 确定凯文·贝肯的 Erdős 数和保罗·Erdős 的贝肯数。11 哪个更难：正确获得图搜索算法还是获得合适的输入图？
9. 考虑 E-BFS 不优于经典 BFS 的图。 什么对策（例如，图预处理步骤）使 E-BFS 重新领先？
10. 找到另一个经典算法，该算法在其输出最终确定后执行不必要的工作。 修复算法并测量改进。
11. 通过分析社交接触图中可能的传染路径来为公共卫生工作提供信息。 使用高效的图搜索来拯救世界。
致谢
普林斯顿大学的 Timothy Chow 和 Robert E. Tarjan 教授审阅了本作品的早期草稿并提供了宝贵的反馈。
参考文献
1. Ahuja, R. K., Magnanti, T. L., Orlin, J. B. 1993. 网络流（第 76 页）。 上萨德尔河，新泽西州：普伦蒂斯霍尔。
2. Anderson, E., Tucek, J. 2010. 效率很重要！ SIGOPS 操作系统评论 44(1):40—45; https://doi.org/10.1145/1740390.1740400。
3. Boost 图库； https://dl.bintray.com/boostorg/release/1.73.0/source/boost_1_73_0.tar.bz2. [Boost 的 BFS 紧随 Cormen 等人的文本。4]
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. 2009. 算法导论，第三版（第 595 页）。 马萨诸塞州剑桥市：麻省理工学院出版社。
5. Dijkstra, E. W. 1968. GOTO 语句被认为有害。 通讯 11(3):147—148; https://doi.org/10.1145/362929.362947。
6. GeeksforGeeks。 图的广度优先搜索或 BFS； https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/。
7. McDowell, G. L. 2016. 破解编码面试，第六版（第 108 页）。 加利福尼亚州帕洛阿尔托：CareerCup。
8. McSherry, F., Isard, M., Murray, D. G. 2015. 可扩展性！ 但代价是什么？ Usenix HotOS XV; https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf。
9. Newman, M. 2010. 网络：导论（第 320 页）。 纽约州纽约市：牛津大学出版社。
10. Orwant, J., Hietaniemi, J., and John Macdonald, J. 1999. 精通 Perl 算法（第 307 页）。 奥莱利。
11. Sedgewick, R., Wayne, K. 2011. 算法，第四版（第 540 页）。 艾迪生-韦斯利专业人士。
12. 维基百科。 广度优先搜索； https://en.wikipedia.org/wiki/Breadth-first_search
特伦斯·凯利 ([email protected]) 是 的杰出成员和终身会员。 他在普林斯顿大学和密歇根大学学习计算机科学，然后在工业研究机构（惠普实验室）担任了 16 年的研究员和软件工程师。 凯利避免所有不必要的工作以及大部分其他类型的工作。
版权所有 © 2020，所有者/作者持有。 出版权已许可给 。
最初发表于 Queue 第 18 卷，第 4 期—
在 数字图书馆 中评论本文
© 保留所有权利。