如何在无向图中高效查找所有bottleneck path（瓶颈路径）？

首先明确：你定义的「瓶颈路径」，本质是移除后会导致原图分裂为两个不连通子图的路径。这类路径的核心特征是：路径上包含至少一个「桥（Bridge）」——也就是移除后会直接导致图分裂的边，且这条路径是两个双连通分量（内部任意两点有至少两条不相交路径的子图）之间的唯一连通通道。

核心算法流程 #

1. 找出所有桥与双连通分量

   • 用Tarjan算法在线性时间O(V+E)内完成：通过深度优先搜索（DFS）遍历图，跟踪每个节点的发现时间和能回溯到的最早祖先节点。对于边u-v，如果low[v] > disc[u]，说明u-v是桥。同时该算法可划分出所有双连通分量。

2. 构建块割树（Block-Cut Tree）

   • 将每个双连通分量视为一个「块节点」，每个桥作为连接两个块节点的边，最终得到一棵树结构（块割树）。在这棵树中，任意两个块节点之间的路径，对应原图中连接这两个双连通分量的唯一通道——也就是你要找的瓶颈路径的核心结构。

3. 枚举所有瓶颈路径

   • 块割树中的每条边（对应原图的桥），两端块节点之间的所有原图路径都是瓶颈路径：移除这些路径中的任意一条，都会断开两个双连通分量的连接，导致原图分裂。
   • 对于块割树中任意两个不同的块节点，它们之间的唯一路径对应原图中一组瓶颈路径——所有连接这两个块节点、且仅经过路径上的桥和对应双连通分量内部路径的路径，都属于瓶颈路径。

实现细节 #

• 实现Tarjan算法时，需记录每个节点所属的双连通分量编号，以及所有桥的集合。
• 构建块割树后，枚举树中所有节点对的路径，即可对应到原图的瓶颈路径结构。如果需要具体的路径实例，可在双连通分量内部枚举所有可能的路径组合（双连通分量内部路径任选，只要连接到桥的两端即可）。
• 若原图本身是双连通的（无桥），则不存在任何瓶颈路径——因为移除任意一条路径，图仍保持连通。

内容的提问来源于stack exchange，提问作者Jonathan L