编辑“︁最小生成树”︁

{{DISPLAYTITLE:最小生成树}}

'''最小生成树'''（Minimum Spanning Tree，MST）是图论中的一个重要概念，指在给定的连通加权无向图中，找到一棵包含所有顶点的生成树，并且这棵树的边权之和最小。最小生成树在计算机网络、交通规划、电力传输等领域有广泛应用。

== 基本概念 ==
给定一个连通无向图<math>G = (V, E)</math>，其中<math>V</math>是顶点集，<math>E</math>是边集，每条边<math>e \in E</math>有一个权重<math>w(e)</math>。最小生成树是<math>G</math>的一个子图<math>T = (V, E')</math>，满足以下条件：
1. <math>T</math>是树（无环且连通）。
2. <math>T</math>包含<math>G</math>的所有顶点。
3. <math>\sum_{e \in E'} w(e)</math>是所有可能的生成树中最小的。

=== 性质 ===
* 最小生成树可能不唯一（如果存在多条边权重相同）。
* 最小生成树的边数为<math>|V| - 1</math>。
* 最小生成树是贪心算法的经典应用之一。

== 算法实现 ==
以下是两种经典的最小生成树算法：'''Kruskal算法'''和'''Prim算法'''。

=== Kruskal算法 ===
Kruskal算法基于贪心策略，按边权重从小到大选择边，同时确保不形成环。

==== 算法步骤 ====
1. 将所有边按权重升序排序。
2. 初始化一个空集合<math>E'</math>。
3. 遍历每条边，如果加入当前边不会形成环，则将其加入<math>E'</math>。
4. 重复步骤3直到<math>|E'| = |V| - 1</math>。

==== 代码示例 ====
以下是Python实现（使用并查集检测环）：

<syntaxhighlight lang="python">
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

def kruskal(graph):
    edges = []
    for u in range(len(graph)):
        for v, weight in graph[u]:
            edges.append((weight, u, v))
    edges.sort()
    
    uf = UnionFind(len(graph))
    mst = []
    for weight, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
        if len(mst) == len(graph) - 1:
            break
    return mst

# 示例输入：邻接表表示的图
graph = [
    [(1, 2), (2, 3)],  # 顶点0的边：(1, 2)表示0-1边权重为2
    [(0, 2), (2, 1), (3, 1)],
    [(0, 3), (1, 1), (3, 5)],
    [(1, 1), (2, 5)]
]
mst = kruskal(graph)
print("Kruskal算法结果：", mst)
</syntaxhighlight>

==== 输出示例 ====
<pre>
Kruskal算法结果： [(1, 3, 1), (1, 2, 1), (0, 1, 2)]
</pre>

=== Prim算法 ===
Prim算法从任意顶点开始，逐步扩展生成树，每次选择连接树和非树顶点的最小权重边。

==== 算法步骤 ====
1. 初始化一个顶点集合<math>V'</math>（初始包含任意一个顶点）。
2. 选择连接<math>V'</math>和<math>V \setminus V'</math>的最小权重边，将其加入生成树。
3. 将新顶点加入<math>V'</math>。
4. 重复步骤2-3直到<math>V' = V</math>。

==== 代码示例 ====
以下是Python实现（使用优先队列）：

<syntaxhighlight lang="python">
import heapq

def prim(graph):
    mst = []
    visited = [False] * len(graph)
    heap = []
    # 从顶点0开始
    heapq.heappush(heap, (0, 0, -1))  # (weight, u, parent)
    
    while heap and len(mst) < len(graph):
        weight, u, parent = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        if parent != -1:
            mst.append((parent, u, weight))
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (w, v, u))
    return mst

# 使用与Kruskal相同的示例图
mst = prim(graph)
print("Prim算法结果：", mst)
</syntaxhighlight>

==== 输出示例 ====
<pre>
Prim算法结果： [(0, 1, 2), (1, 3, 1), (1, 2, 1)]
</pre>

== 算法对比 ==
{| class="wikitable"
|+ Kruskal与Prim算法对比
|-
! 算法 !! 时间复杂度 !! 适用场景
|-
| Kruskal || <math>O(E \log E)</math> || 稀疏图（边少）
|-
| Prim（二叉堆） || <math>O(E \log V)</math> || 稠密图（边多）
|}

== 实际应用 ==
=== 网络设计 ===
在计算机网络中，最小生成树用于设计成本最低的连接方案，例如：
* 数据中心服务器之间的布线。
* 城市间光纤网络的铺设。

=== 交通规划 ===
在城市道路规划中，最小生成树可以帮助设计连接所有区域的最短道路网络。

=== 电力传输 ===
电力公司使用最小生成树确定输电线路的最优布局，以最小化电缆成本。

== 可视化示例 ==
以下是一个图及其最小生成树的Mermaid表示：

<mermaid>
graph TD
    A((A)) --2--- B((B))
    A --3--- C((C))
    B --1--- C
    B --1--- D((D))
    C --5--- D

    subgraph 最小生成树
        B --1--- C
        B --1--- D
        A --2--- B
    end
</mermaid>

== 数学基础 ==
最小生成树的构造依赖于以下定理：
* '''切割性质'''：对于图的任意切割（将顶点分为两部分），横跨切割的最小权重边属于某个最小生成树。
* '''循环性质'''：对于图中的任意环，环中最大权重的边不属于任何最小生成树。

数学表达：
* 切割性质：若边<math>e</math>是横跨切割的最小权重边，则存在一棵MST包含<math>e</math>。
* 循环性质：若边<math>e</math>是环<math>C</math>中的最大权重边，则不存在包含<math>e</math>的MST。

== 扩展阅读 ==
* 其他MST算法：Borůvka算法（适用于并行计算）。
* 动态MST问题：如何在图动态变化时高效维护MST。
* 次小生成树：权值和第二小的生成树。

== 总结 ==
最小生成树是图论中的核心问题，其算法（如Kruskal和Prim）是贪心策略的典型应用。理解MST不仅有助于解决实际问题，也为学习更复杂的图算法奠定基础。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:搜索算法]]