最小生成树—Prim（普里姆）算法
一、算法概述
Prim 算法是一种用于求解加权无向连通图的最小生成树（MST） 的贪心算法。它从一个顶点开始，逐步扩展生成树，每次选择连接已选顶点集和未选顶点集的最小权重边。
二、算法思想
初始化：从任意顶点开始，将其加入生成树集合
重复执行：
在所有连接已选顶点和未选顶点的边中，选择权重最小的边
将该边加入生成树，并将对应的未选顶点加入已选集合
终止条件：当所有顶点都加入生成树时结束
三、算法过程示例
示例图（顶点：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，一端不在 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}
最小生成树—Kruskal（克鲁斯卡尔）算法
一、算法描述
在一个连通加权无向图中，找到一棵最小生成树。即，找到连接所有顶点的、权值总和最小的树，且树中不包含任何环。
二、核心思想
贪心策略：每次从未选择的边中，选取一条权值最小的边。
避免环路：如果加入这条边会导致生成树中形成环，则舍弃它。
集合管理：使用并查集数据结构来高效地判断两个顶点是否已经连通（即加入边是否会形成环）。
三、图解过程
假设我们有以下连通图 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}