数据结构：最小生成树

1.基本概念

• 生成树：连通无向图的生成树是包含图中所有顶点的极小连通子图（无环）。

• 最小生成树：所有生成树中边权重总和最小的那棵。

2.常用算法

克鲁斯卡尔算法（Kruskal）

1. 步骤：

   • 将所有边按权重升序排序。

   • 依次选择边，若其连接两个不同连通分量（不形成环），则加入生成树。

   • 使用并查集（Union-Find）高效管理连通性。

2. 时间复杂度：O(E log E)（排序和并查集操作）。

3. 适用场景：稀疏图（边较少）。

普里姆算法（Prim）

1. 步骤：

   • 从任一顶点开始，逐步扩展。

   • 每次选择连接已选顶点集和未选顶点集的最小权重边。

   • 使用优先队列（如堆）维护候选边。

2. 时间复杂度：

   • 二叉堆：O(E log V)

   • 斐波那契堆：O(E + V log V)（更优）。

3. 适用场景：稠密图（边较多）。

3.具体例子：

假设有一个无向图，包含 4个顶点（A, B, C, D） 和 6条边，权重如下：

• AB: 权重 1

• AC: 权重 3

• AD: 权重 4

• BC: 权重 2

• BD: 权重 5

• CD: 权重 6

目标：找到该图的最小生成树（总权重最小）。

1. 克鲁斯卡尔算法（Kruskal）示例

步骤：

1. 按权重升序排序所有边：

AB(1) → BC(2) → AC(3) → AD(4) → BD(5) → CD(6)

1. 初始化并查集：每个顶点自成一个集合。

2. 依次选择边并检查是否形成环：

   • 选择 AB(1)：连接 A 和 B（不同集合），合并集合。
     已选边：AB(1)
     总权重：1
     顶点集合：{A, B}, {C}, {D}

   • 选择 BC(2)：连接 B 和 C（不同集合），合并集合。
     已选边：AB(1), BC(2)
     总权重：1+2=3
     顶点集合：{A, B, C}, {D}

   • 选择 AC(3)：A 和 C 已属于同一集合（形成环），跳过。

   • 选择 AD(4)：连接 A 和 D（不同集合），合并集合。
     已选边：AB(1), BC(2), AD(4)
     总权重：1+2+4=7
     顶点集合：{A, B, C, D}（所有顶点连通）

   • 此时已选 3 条边（V-1=3），算法终止。

最终最小生成树：

A — B (1)
B — C (2)
A — D (4)

2. 普里姆算法（Prim）示例

步骤：

1. 从顶点 A 开始，初始化优先队列（最小堆）。

2. 逐步扩展生成树：

   • 初始状态：已访问顶点 {A}，候选边为 A 的邻边 AB(1)、AC(3)、AD(4)。
     优先队列：AB(1), AC(3), AD(4)

   • 选择 AB(1)：连接 A 和 B，标记 B 为已访问。
     已选边：AB(1)
     总权重：1
     候选边更新：添加 B 的邻边 BC(2)、BD(5)。
     优先队列：BC(2), AC(3), AD(4), BD(5)

   • 选择 BC(2)：连接 B 和 C，标记 C 为已访问。
     已选边：AB(1), BC(2)
     总权重：1+2=3
     候选边更新：添加 C 的邻边 CD(6)。
     优先队列：AC(3), AD(4), BD(5), CD(6)

   • 选择 AC(3)：A 和 C 已连通（C 已访问），跳过。

   • 选择 AD(4)：连接 A 和 D，标记 D 为已访问。
     已选边：AB(1), BC(2), AD(4)
     总权重：1+2+4=7
     所有顶点已访问，算法终止。

最终最小生成树：

A — B (1)
B — C (2)
A — D (4)

关键结论

• 克鲁斯卡尔：按边权重排序，逐步合并不连通的子树。

• 普里姆：从起点扩展，每次选择连接已访问和未访问顶点的最小边。

• 两种算法结果相同：因为示例图权重唯一，生成的最小生成树唯一。