相关概念
连通图与它的生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图的顶点数为n，则它的生成树含有n-1条边。一个连通图可能拥有多个生成树。
最小生成树（Minimum-Spanning-Tree，MST）
对于一个带权连通无向图，它的生成树中边权之和最小的那一个，称为最小生成树。
一个连通图的最小生成树是不唯一的。边权值之和唯一，但树的形状不唯一。
接下来介绍的Prim算法和Kruskal算法，都是基于贪心算法的。
Prim算法
核心思路
此算法又称为“加点法”，每次遍历选择权最小的边对应的点，加入到最小生成树中；然后尝试更新剩余的点到最小生成树的最小边权。算法从某个顶点开始，直到最小生成树有n个顶点为止。
算法图解
伪码实现
void Prim(Graph) {Tree = ∅;// 初始化空树Tree.add(v);// 添加任意顶点minCost[];// 顶点到树的最小代价for (int i = 1; i < graphSize; i++) {// 计数，循环执行(顶点数-1)次// for循环找到距离树代价最小的顶点vfor(int j = 0; j < graphSize; i++) {v = findMinCostVertex();}// 顶点入树Tree.add(v);// for循环维护顶点到树的最小代价for(int j = 0; j < graphSize; i++) {minCost[];}}}
复杂度分析
Prim算法的时间复杂度是O(V²)，不依赖于E。
因此，它适合求解边稠密的图（边多点少）的最小生成树问题。
Kruskal算法
核心思路
此算法又称为“加边法”，初始化时将所有顶点看作独立的树，然后每次连通最小的边的两端顶点（先对边进行排序）；如果两个顶点本来就连通，则跳过；直到只有一个连通分量。
算法图解
伪码实现
void Kruskal(Graph) {Collections.sort(Edges);// 先对边进行排序 Tree = new UnionSet(n);// 初始化树while (unionSize > 1) {// 当连通分量大于1时，说明有的点还没连上e = Edges.poll();// 取出最小边if (!unionSet.isUnion(e.v1, e.v2)) {// 如果该边的两个顶点还未连通unionSet.union(e.v1, e.v2);// 则连通它们unionSize--;// 并且连通分量减1}}}
复杂度分析
Kruskal算法的时间复杂度是O(ElogE)，不依赖于V。
因此，它适合求解边稀疏的图（点多边少）的最小生成树问题。
☘️
