最小瓶颈生成树算法
字数 3068 2025-12-10 01:46:16
好的，我们来学习一个尚未在列表中出现的重要图论算法。
最小瓶颈生成树算法
1. 题目描述
给定一个带权无向连通图 \(G = (V, E)\) ，每条边 \(e \in E\) 有权重 \(w(e)\) 。
定义一棵生成树的瓶颈值为这棵生成树中权重最大的边的权重。
我们需要找到所有生成树中瓶颈值最小的那一棵（或那些）生成树，并求出这个最小的瓶颈值。
这个问题称为最小瓶颈生成树问题（Minimum Bottleneck Spanning Tree, MBST）。
2. 问题理解与性质
2.1 什么是瓶颈生成树？
举例来说：
- 图有 4 个顶点，边权重分别为：
\((1,2): 10\), \((2,3): 1\), \((3,4): 2\), \((1,4): 5\), \((1,3): 7\)
- 某棵生成树包含边 \(\{ (1,2):10, (2,3):1, (1,4):5 \}\) ，则它的瓶颈值 = 10（因为最大边权重是10）。
- 另一棵生成树包含边 \(\{ (1,4):5, (1,3):7, (2,3):1 \}\) ，瓶颈值 = 7 。
我们要找瓶颈值最小的生成树。
2.2 一个重要性质
最小生成树（MST）就是一棵最小瓶颈生成树。
这个性质来自一个事实：
假设 \(T\) 是一棵 MST（按 Kruskal 或 Prim 算法得到的），它的最大边权是 \(w_{\max}(T)\) 。
如果存在另一棵生成树 \(T'\) 的最大边权 \(w_{\max}(T') < w_{\max}(T)\) ，那么 \(T'\) 的所有边权都 \(\le w_{\max}(T')\) ，这意味着这些边都比 \(T\) 中的最大边小。
但 Kruskal 算法添加边的顺序是按权重从小到大，在添加 \(w_{\max}(T)\) 之前，这些更小的边不足以连通所有顶点（否则 MST 就不会选这条最大边），所以 \(T'\) 不可能存在。
因此 MST 的瓶颈值是最小的。
3. 算法思路
既然 MST 就是 MBST，那么直接求 MST 即可得到答案。
但有时候我们不想完全生成 MST，只想知道最小的瓶颈值，或者在某些特殊情况下想更快得到 MBST（例如边权范围有限时）。
方法一：求 MST
直接用 Kruskal 或 Prim 算法得到 MST，然后找出 MST 中最大边权。
时间复杂度：
- Kruskal: \(O(|E| \log |E|)\)
- Prim: \(O(|E| + |V| \log |V|)\) （二叉堆优化）
方法二：二分搜索 + 连通性检查
直接找最小瓶颈值 \(B\) 的算法：
- 猜测一个瓶颈值 \(x\) 。
- 在图中只保留权重 \(\le x\) 的边，检查这个子图是否连通（用 BFS/DFS 或并查集）。
- 如果连通，说明存在一棵生成树的最大边权 \(\le x\) ，所以真实的瓶颈值 \(\le x\) ，可以尝试更小的 \(x\) 。
- 如果不连通，说明所有生成树都至少有一条边权重 > \(x\) ，所以瓶颈值必须 > \(x\) ，尝试更大的 \(x\) 。
- 二分搜索 \(x\) 在所有边权中的可能取值，直到找到最小的可行 \(x\) 。
优势：当边权是整数且范围不大时，二分搜索的次数是 \(O(\log W)\) ，每次检查连通性 \(O(|V|+|E|)\) ，总共 \(O((|V|+|E|) \log W)\) ，可能比排序边更快（如果 \(W\) 很小）。
4. 算法步骤（以二分搜索方法为例）
设边权数组为 \(W = [w_1, w_2, \dots, w_m]\) ，并假设它们是整数（或可离散化）。
- 将 \(W\) 排序，得到唯一权重列表 \([c_1, c_2, \dots, c_k]\) ， \(c_1 < c_2 < \dots < c_k\) 。
- 初始化 \(low = 1\), \(high = k\) 。
- 当 \(low < high\) ：
- \(mid = \lfloor (low+high)/2 \rfloor\)
- 在 \(G\) 中只保留权重 \(\le c_{mid}\) 的边，得到子图 \(G_{mid}\)
- 检查 \(G_{mid}\) 是否连通（可以用并查集）
- 如果连通：\(high = mid\)
- 否则：\(low = mid + 1\)
- 循环结束时，\(c_{low}\) 就是最小瓶颈值。
- （可选）为了得到一棵 MBST，可以用 Kruskal 算法但只考虑权重 \(\le c_{low}\) 的边，构造一棵生成树。
5. 举例说明
图：顶点 \(\{A,B,C,D\}\)
边：
- \(AB: 8\)
- \(BC: 3\)
- \(CD: 6\)
- \(DA: 5\)
- \(AC: 7\)
- \(BD: 9\)
唯一权重排序： \([3,5,6,7,8,9]\)
二分搜索过程：
-
low=1, high=6 → mid=3 → c[3]=6
保留权重 ≤6 的边： BC(3), CD(6), DA(5), AC(7)? 不，AC=7>6 去掉，AB=8>6 去掉，BD=9>6去掉。
剩余边： BC, CD, DA
检查连通性：
A--D--C--B ，连通所有顶点吗？ A-D, D-C, C-B 可以连通 A,B,C,D 吗？
A 到 B：A→D→C→B ✅ 连通
所以可行，high=3
-
low=1, high=3 → mid=2 → c[2]=5
保留权重 ≤5 的边： BC(3), DA(5)
图不连通（只有两条边，顶点 A 与 D 连，B 与 C 连，但这两组之间没有边）
所以不可行，low=3
-
low=3, high=3 → 结束
最小瓶颈值 = \(c[3] = 6\)
构造 MBST：
用 Kruskal 在权重 ≤6 的边中构造生成树：
- 排序权重 ≤6 的边： BC(3), DA(5), CD(6)
- 选 BC，选 DA，选 CD（检查不形成环），得到树 BC, DA, CD
总边数=3，连通 4 个顶点，瓶颈值=6。
6. 时间复杂度分析
- 排序边权去重：\(O(|E| \log |E|)\)
- 二分搜索：\(O(\log |E|)\) 次
- 每次连通性检查（用 BFS/DFS）：\(O(|V|+|E|)\)
总复杂度： \(O(|E| \log |E| + (|V|+|E|) \log |E|) = O((|V|+|E|) \log |E|)\)
通常这和直接求 MST 差不多，但二分法在某些情况下（比如边权范围很小）可更优。
7. 总结
- 最小瓶颈生成树问题（MBST）等价于求最小生成树（MST）的瓶颈值。
- 可直接用 MST 算法得到答案。
- 二分搜索 + 连通性检查是另一种直接求最小瓶颈值的思路，避免了完全排序所有边（如果边权可快速索引）。
- 关键性质：MST 就是一棵 MBST，所以最小瓶颈值等于 MST 中最大边权。
好的，我们来学习一个尚未在列表中出现的重要图论算法。 最小瓶颈生成树算法 1. 题目描述 给定一个 带权无向连通图 \( G = (V, E) \) ，每条边 \( e \in E \) 有权重 \( w(e) \) 。 定义一棵生成树的 瓶颈值 为这棵生成树中 权重最大的边 的权重。 我们需要找到 所有生成树中瓶颈值最小 的那一棵（或那些）生成树，并求出这个最小的瓶颈值。 这个问题称为 最小瓶颈生成树问题 （Minimum Bottleneck Spanning Tree, MBST）。 2. 问题理解与性质 2.1 什么是瓶颈生成树？ 举例来说： 图有 4 个顶点，边权重分别为： \( (1,2): 10 \), \( (2,3): 1 \), \( (3,4): 2 \), \( (1,4): 5 \), \( (1,3): 7 \) 某棵生成树包含边 \( \{ (1,2):10, (2,3):1, (1,4):5 \} \) ，则它的瓶颈值 = 10（因为最大边权重是10）。 另一棵生成树包含边 \( \{ (1,4):5, (1,3):7, (2,3):1 \} \) ，瓶颈值 = 7 。 我们要找瓶颈值最小的生成树。 2.2 一个重要性质 最小生成树（MST）就是一棵最小瓶颈生成树 。 这个性质来自一个事实： 假设 \( T \) 是一棵 MST（按 Kruskal 或 Prim 算法得到的），它的最大边权是 \( w_ {\max}(T) \) 。 如果存在另一棵生成树 \( T' \) 的最大边权 \( w_ {\max}(T') < w_ {\max}(T) \) ，那么 \( T' \) 的所有边权都 \( \le w_ {\max}(T') \) ，这意味着这些边都比 \( T \) 中的最大边小。 但 Kruskal 算法添加边的顺序是按权重从小到大，在添加 \( w_ {\max}(T) \) 之前，这些更小的边不足以连通所有顶点（否则 MST 就不会选这条最大边），所以 \( T' \) 不可能存在。 因此 MST 的瓶颈值是最小的。 3. 算法思路 既然 MST 就是 MBST，那么直接求 MST 即可得到答案。 但 有时候我们不想完全生成 MST ，只想知道最小的瓶颈值，或者在某些特殊情况下想更快得到 MBST（例如边权范围有限时）。 方法一：求 MST 直接用 Kruskal 或 Prim 算法得到 MST，然后找出 MST 中最大边权。 时间复杂度： Kruskal: \( O(|E| \log |E|) \) Prim: \( O(|E| + |V| \log |V|) \) （二叉堆优化） 方法二：二分搜索 + 连通性检查 直接找最小瓶颈值 \( B \) 的算法： 猜测一个瓶颈值 \( x \) 。 在图中只保留权重 \( \le x \) 的边，检查这个子图是否连通（用 BFS/DFS 或并查集）。 如果连通，说明存在一棵生成树的最大边权 \( \le x \) ，所以真实的瓶颈值 \( \le x \) ，可以尝试更小的 \( x \) 。 如果不连通，说明所有生成树都至少有一条边权重 > \( x \) ，所以瓶颈值必须 > \( x \) ，尝试更大的 \( x \) 。 二分搜索 \( x \) 在所有边权中的可能取值，直到找到最小的可行 \( x \) 。 优势 ：当边权是整数且范围不大时，二分搜索的次数是 \( O(\log W) \) ，每次检查连通性 \( O(|V|+|E|) \) ，总共 \( O((|V|+|E|) \log W) \) ，可能比排序边更快（如果 \( W \) 很小）。 4. 算法步骤（以二分搜索方法为例） 设边权数组为 \( W = [ w_ 1, w_ 2, \dots, w_ m ] \) ，并假设它们是整数（或可离散化）。 将 \( W \) 排序，得到唯一权重列表 \( [ c_ 1, c_ 2, \dots, c_ k] \) ， \( c_ 1 < c_ 2 < \dots < c_ k \) 。 初始化 \( low = 1 \), \( high = k \) 。 当 \( low < high \) ： \( mid = \lfloor (low+high)/2 \rfloor \) 在 \( G \) 中只保留权重 \( \le c_ {mid} \) 的边，得到子图 \( G_ {mid} \) 检查 \( G_ {mid} \) 是否连通（可以用并查集） 如果连通：\( high = mid \) 否则：\( low = mid + 1 \) 循环结束时，\( c_ {low} \) 就是最小瓶颈值。 （可选）为了得到一棵 MBST，可以用 Kruskal 算法但只考虑权重 \( \le c_ {low} \) 的边，构造一棵生成树。 5. 举例说明 图：顶点 \( \{A,B,C,D\} \) 边： \( AB: 8 \) \( BC: 3 \) \( CD: 6 \) \( DA: 5 \) \( AC: 7 \) \( BD: 9 \) 唯一权重排序： \( [ 3,5,6,7,8,9 ] \) 二分搜索过程 ： low=1, high=6 → mid=3 → c[ 3 ]=6 保留权重 ≤6 的边： BC(3), CD(6), DA(5), AC(7)? 不，AC=7>6 去掉，AB=8>6 去掉，BD=9>6去掉。 剩余边： BC, CD, DA 检查连通性： A--D--C--B ，连通所有顶点吗？ A-D, D-C, C-B 可以连通 A,B,C,D 吗？ A 到 B：A→D→C→B ✅ 连通 所以可行，high=3 low=1, high=3 → mid=2 → c[ 2 ]=5 保留权重 ≤5 的边： BC(3), DA(5) 图不连通（只有两条边，顶点 A 与 D 连，B 与 C 连，但这两组之间没有边） 所以不可行，low=3 low=3, high=3 → 结束 最小瓶颈值 = \( c[ 3 ] = 6 \) 构造 MBST ： 用 Kruskal 在权重 ≤6 的边中构造生成树： 排序权重 ≤6 的边： BC(3), DA(5), CD(6) 选 BC，选 DA，选 CD（检查不形成环），得到树 BC, DA, CD 总边数=3，连通 4 个顶点，瓶颈值=6。 6. 时间复杂度分析 排序边权去重 ：\( O(|E| \log |E|) \) 二分搜索 ：\( O(\log |E|) \) 次 每次连通性检查（用 BFS/DFS）：\( O(|V|+|E|) \) 总复杂度： \( O(|E| \log |E| + (|V|+|E|) \log |E|) = O((|V|+|E|) \log |E|) \) 通常这和直接求 MST 差不多，但二分法在某些情况下（比如边权范围很小）可更优。 7. 总结 最小瓶颈生成树问题（MBST）等价于求最小生成树（MST）的瓶颈值。 可直接用 MST 算法得到答案。 二分搜索 + 连通性检查是另一种直接求最小瓶颈值的思路，避免了完全排序所有边（如果边权可快速索引）。 关键性质：MST 就是一棵 MBST，所以最小瓶颈值等于 MST 中最大边权。
