一、算法概述

Prim 算法是一种用于求解加权无向连通图的最小生成树（MST） 的贪心算法。它从一个顶点开始，逐步扩展生成树，每次选择连接已选顶点集和未选顶点集的最小权重边。

二、算法思想

1. 初始化：从任意顶点开始，将其加入生成树集合

2. 重复执行：

• 在所有连接已选顶点和未选顶点的边中，选择权重最小的边

• 将该边加入生成树，并将对应的未选顶点加入已选集合

3. 终止条件：当所有顶点都加入生成树时结束

三、算法过程示例

示例图（顶点：A,B,C,D；边权重如图）：

更清晰的邻接关系（无向图，权重如图）：

• A–B : 2

• A–C : 4

• A–D : 3

• B–D : 1

• C–D : 5

顶点集合：{A, B, C, D}

目标：用 Prim 算法找最小生成树（MST）。

每次选择连接 已选顶点集 与 未选顶点集 的最小权重边，将该边及其另一端点加入已选集合。

步骤 1

• 已选集合 $S=\{A\}$

• 候选边（一端在 S，一端不在 S）：

• A–B (2)   （说明:A在S中，B不在S中）

• A–C (4)   （说明:A在S中，C不在S中）

• A–D (3)   （说明:A在S中，D不在S中）

• 最小权重边：A–B (2)

• 加入 B 到 S，边 A–B 加入 MST。

MST 边：{A–B}

S = {A, B}

一、算法描述

在一个连通加权无向图中，找到一棵最小生成树。即，找到连接所有顶点的、权值总和最小的树，且树中不包含任何环。

二、核心思想

1. 贪心策略：每次从未选择的边中，选取一条权值最小的边。

2. 避免环路：如果加入这条边会导致生成树中形成环，则舍弃它。

3. 集合管理：使用并查集数据结构来高效地判断两个顶点是否已经连通（即加入边是否会形成环）。

三、图解过程

假设我们有以下连通图 G，目标是找到它的最小生成树（MST）。

步骤 0：初始化

• 将图中所有边按权值从小到大排序。

• 初始化一个空的边集 MST，用于存放最小生成树的边。

• 初始化并查集，让每个顶点自成一個集合。

排序后的边列表：(A,D):5, (C,E):5, (D,F):6, (A,B):7, (B,E):7, (B,C):8, (E,F):8, (B,D):9, ...

当前 MST： { }并查集状态： {A}, {B}, {C}, {D}, {E}, {F}