一、算法概述

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}