一、什么是生成树和最小生成树？¶
在数据结构中，图是由顶点（也叫节点）和边组成的结构。生成树是指连通无向图的一个子图，它包含图中所有的顶点，并且没有环（即树的性质：n个顶点有n-1条边，且任意两个顶点之间有且仅有一条路径）。
举个例子：如果有4个城市（顶点）A、B、C、D，它们之间的道路（边）连接起来，形成一个没有重复道路和闭环的网络，这就是一个生成树。而最小生成树（Minimum Spanning Tree, MST） 则是所有可能的生成树中，边权值之和最小的那一棵。
比如，城市间的道路有不同的长度（权值），我们希望找到连接所有城市且总长度最短的道路网络，这就是最小生成树的问题。
二、贪心算法：为什么最小生成树适合贪心？¶
贪心算法的核心思想是“每一步都选择当前最优解，最终得到全局最优解”。最小生成树恰好符合贪心算法的适用场景，因为：
- 生成树必须包含所有顶点，且边数为n-1（n为顶点数）。
- 我们只需要考虑“局部最优”的边选择：每次选择连接“已选顶点集合”和“未选顶点集合”的最小权边，就能逐步构建出总权值最小的生成树。
三、Prim算法的基本思路¶
Prim算法是最小生成树的经典贪心算法之一，核心步骤如下：
- 初始化：任选一个顶点作为起点（例如顶点v₀），将其标记为“已选顶点”。
- 重复扩展：每次从“已选顶点集合”和“未选顶点集合”之间的所有边中，选择权值最小的那条边，将对应的未选顶点加入“已选顶点集合”。
- 终止条件：当所有顶点都被加入“已选顶点集合”时，生成树构建完成。
四、算法步骤详解（附实例）¶
为了直观理解，我们用一个简单的例子演示Prim算法：
示例图：有4个顶点A、B、C、D，边及其权值如下：
- A-B: 2，A-C: 3，B-C: 1，B-D: 4，C-D: 5
顶点编号：A=0，B=1，C=2，D=3。
步骤1：选择起点¶
任选一个起点，比如选A（顶点0）。此时：
- 已选顶点集合 S = {0}（仅包含A）
- 未选顶点集合 U = {1, 2, 3}（B、C、D）
步骤2：寻找最小边并扩展¶
重复以下操作，直到所有顶点被选中：
第一次迭代：¶
S = {0}，U = {1, 2, 3}
需要找S（0）和U（1,2,3）之间的所有边：
- A-B（0-1）: 权值2
- A-C（0-2）: 权值3
最小边是A-B（权值2）。将B（1）加入S：
S = {0, 1}，U = {2, 3}
第二次迭代：¶
S = {0, 1}，U = {2, 3}
需要找S（0,1）和U（2,3）之间的所有边：
- A-C（0-2）: 权值3
- B-C（1-2）: 权值1
- B-D（1-3）: 权值4
最小边是B-C（权值1）。将C（2）加入S：
S = {0, 1, 2}，U = {3}
第三次迭代：¶
S = {0, 1, 2}，U = {3}
需要找S（0,1,2）和U（3）之间的所有边：
- A-D（无直接边）
- B-D（1-3）: 权值4
- C-D（2-3）: 权值5
最小边是B-D（权值4）。将D（3）加入S：
S = {0, 1, 2, 3}，所有顶点已选入。
最终最小生成树¶
选中的边为：A-B（2）、B-C（1）、B-D（4），总权值=2+1+4=7。
五、算法实现与细节¶
1. 数据结构表示¶
图可以用邻接矩阵或邻接表表示。对于初学者，邻接矩阵更直观（二维数组），例如：
graph = [
[0, 2, 3, 0], # A的邻接：A-B=2，A-C=3
[2, 0, 1, 4], # B的邻接：B-A=2，B-C=1，B-D=4
[3, 1, 0, 5], # C的邻接：C-A=3，C-B=1，C-D=5
[0, 4, 5, 0] # D的邻接：D-B=4，D-C=5
]
其中graph[i][j]表示顶点i和j之间的边权值（0表示无边）。
2. 核心步骤伪代码¶
// Prim算法伪代码
function Prim(graph, n):
// n为顶点数，graph为邻接矩阵
key = [INF] * n // key数组：记录未选顶点到已选集合的最小边权
parent = [-1] * n // parent数组：记录生成树的父节点
key[0] = 0 // 从顶点0开始（起点）
selected = [False] * n // 标记顶点是否已选入S
for i from 0 to n-1:
// 找到未选顶点中key最小的u
u = 找到key最小且selected[u]=False的顶点
selected[u] = True // 将u加入已选集合
// 更新未选顶点的key值
for v from 0 to n-1:
if graph[u][v] > 0 and not selected[v] and graph[u][v] < key[v]:
key[v] = graph[u][v]
parent[v] = u
// 计算总权值
total_weight = sum(key[1..n-1]) // 起点key为0，其他为加入的边权
return total_weight, parent
3. 时间复杂度¶
- 使用邻接矩阵时，外层循环n次，内层循环n次，总复杂度为O(n²)（n为顶点数），适合顶点数较少的稠密图。
- 若用邻接表+优先队列优化，复杂度可降至O(m log n)（m为边数），适合稀疏图。
六、Prim算法的关键思想¶
- 贪心选择：每次选择“连接已选集合和未选集合的最小边”，确保局部最优。
- 安全边性质：无论从哪个顶点开始，最终得到的生成树总权值一定最小（证明需数学归纳法，初学者可理解为贪心的合理性）。
七、应用场景¶
- 网络布线：城市间铺设光纤，使总费用最低。
- 电路设计：用最少导线连接所有电子元件，成本最低。
- 交通规划：规划道路，使总长度最短且覆盖所有区域。
总结¶
最小生成树是贪心算法的经典应用，Prim算法通过“从起点逐步扩展，每次选最小边”的策略，高效构建出总权值最小的生成树。理解其核心思想（贪心选择）和步骤，对解决图论问题（如最短路径、网络优化）至关重要。对于初学者，关键是通过具体例子（如本文中的4顶点图）熟悉算法流程，逐步掌握其实现细节。