返回分类：全部文章 >> 基础知识
返回上级：编程基础 - 图 (Graph)
本文将介绍最小生成树的基础知识，并用C++实现克鲁斯卡尔算法(Kruskal)和普利姆算法(Prim)。
在查看本文之前，需要一些数据结构和程序语言的基础。
尤其是“矩阵”、“矩阵的压缩(matrix)”、“图(graph)”、“队列(queue)”等的知识。
对图使用不同的遍历方法，可得到不同的生成树；
从不同的顶点出发也能得到不通过的生成树。
有 n 个顶点的连通且带权的图由 n-1 条边；
最小生成树：
使用 n-1 条边连接网络中的 n 个顶点；且不能使其产生回路；各条边的权值总和最小。重要结论：
当权值各边都不同时，最小生成树一定唯一；当权值部分相同时： 邻接矩阵：由于选边顺序固定，则最小生成树唯一；邻接表：由于边链表不唯一，则最小生成树不唯一。（1）构造一个只有原连通带权图顶点的新图，即没有边只有顶点（每个顶点都是一个连通分量）；
（2）从原连通带权图所有边中选择权值最小的边，如果此边两顶点落在新图中不同的连通分量上，则将此边加入新图，将此边舍去；
（3）重复步骤（2），直到所有顶点同时在一个连通分量上。
假设原连通带权图：
25 9 16 13 11 22 19 23 24 A B C D E F G根据此思想描述生成过程：
Kruskal Step 1 无边新图 25 9 16 13 11 22 19 23 24 A B C D E F G Kruskal Step 2 25 9 16 13 11 22 19 23 24 A B C D E F G Kruskal Step 3 25 9 16 13 11 22 19 23 24 A B C D E F G Kruskal Step 4 25 9 16 13 11 22 19 23 24 A B C D E F G Kruskal Step 5 25 9 16 13 11 22 19 23 24 A B C D E F G Kruskal Step 6 D - G 有回路不能选 25 9 16 13 11 22 19 23 24 A B C D E F G Kruskal Step 7 25 9 16 13 11 22 19 23 24 A B C D E F G Kruskal 最终得到的最小生成树的图 25 9 16 13 11 22 19 23 24 A B C D E F G（1）首先，我们要获取所有的边，还要知道它所连接的顶点，这需要一个数据结构：
// 边 typedef struct KruskalEdge { int first; // 第一个顶点下标 int second; // 第二个顶点下标 double weight; // 两顶点边的权值 KruskalEdge() : first(-1), second(-1), weight(0.0) { } } PrimEdge;（2）其次，我们需要挑选最小权值的边，这可以使用多种排序方法实现；
（3）最后，我们要判断其边两顶点是否在不同的连通分量上 （按图的边） ，这可以使用并查集来实现。
（1）创建只有顶点的图：
// Author: https://blog.csdn.net/DarkRabbit // Minimum Spanning Tree // 创建只复制顶点的图 // params: // graph: 需要复制的图 AMGraphInt* CreateCopyVertexesGraph(AMGraphInt* graph) { int size = graph->GetVertexCount(); // 顶点数量 // 获取所有结点值 std::vector<int> elements = std::vector<int>(size, 0); for (int i = 0; i < size; i++) { graph->TryGetVertex(i, elements[i]); } AMGraphInt* copyGraph = new AMGraphInt(elements, false); // 创建新的无向图 return copyGraph; }（2）获取图的所有边，并从小到大排序：
// Author: https://blog.csdn.net/DarkRabbit // Minimum Spanning Tree // 获取所有边信息 // params: // graph: 获取边的图 // edges: 获取的所有边，并按从小到大排序 void GetAndSortKruskalEdges(AMGraphInt* graph, std::vector<KruskalEdge>& edges) { int size = graph->GetVertexCount(); KruskalEdge edge; for (int r = 0; r < size; r++) { for (int c = 0; c < r; c++) // 无向图，只需下三角 { graph->TryGetWeight(r, c, edge.weight); // 获取权重 if (edge.weight != graph->GetDefaultWeight()) // 如果两点有边 { edge.first = r; edge.second = c; edges.push_back(edge); } } } std::sort(edges.begin(), edges.end(), [](KruskalEdge& lhs, KruskalEdge& rhs)->bool { return lhs.weight < rhs.weight; }); // 从小到大排序 }（3）并查集的查找与并集操作：
// Author: https://blog.csdn.net/DarkRabbit // Minimum Spanning Tree // 并查集 Find，寻找集合中的根 // params: // vertexSet: 并查集 // val: 查找值 // return： // int: 返回集合根下标 int UfsetFind(std::vector<int>& vertexSet, int val) { while (vertexSet[val] >= 0) { val = vertexSet[val]; } return val; } // 并查集 Union，合并集合，将元素少的集合合并入元素多的集合 // params: // vertexSet: 并查集 // set1: 集合1 // set2: 集合2 // return: // int: 成为根的集合 int UfsetUnion(std::vector<int>& vertexSet, int set1, int set2) { int val = vertexSet[set1] + vertexSet[set2]; // 两个集合元素总数量 if (vertexSet[set1] > vertexSet[set2]) { vertexSet[set2] = val; // 集合2成为根 vertexSet[set1] = set2; return set2; } else { vertexSet[set1] = val; // 集合1成为根 vertexSet[set2] = set1; return set1; } }（4）克鲁斯卡尔算法：
// Author: https://blog.csdn.net/DarkRabbit // Minimum Spanning Tree // 克鲁斯卡尔算法 // params: // graph: 需要计算的图 // paths: 输出的连接顺序 // return: // AdjacencyMatrix<int>: 输出的最小生成树的图 AMGraphInt* Kruskal(AMGraphInt* graph, std::vector<KruskalEdge>& paths) { if (graph == nullptr || graph->IsOriented()) // 如果是有序图返回 { return nullptr; } AMGraphInt* minTree = CreateCopyVertexesGraph(graph); // 只复制顶点后的图 int size = minTree->GetVertexCount(); // 顶点数量 if (size <= 1) // 只有零到一个顶点，直接返回 { return minTree; } std::vector<KruskalEdge> edges; // 边 GetAndSortKruskalEdges(graph, edges); // 获取所有边，并按从小到大排序 // 初始化并查集，每个结点为一个集合 std::vector<int> vertexSet = std::vector<int>(size, -1); // 循环使用并查集加入每一条边 for (int i = 0; i < edges.size(); i++) { int set1 = UfsetFind(vertexSet, edges[i].first); // 获取第一个顶点所在集合 int set2 = UfsetFind(vertexSet, edges[i].second); // 获取第二个顶点所在集合 if (set1 != set2) // 不在同一集合 { UfsetUnion(vertexSet, set1, set2); // 合并集合 minTree->TryPutWeight(edges[i].first, edges[i].second, edges[i].weight); // 设置边 minTree->TryPutWeight(edges[i].second, edges[i].first, edges[i].weight); // 设置边 paths.push_back(edges[i]); } } return minTree; }（1）构造一个只有原连通带权图顶点的新图，即没有边只有顶点（每个顶点都是一个连通分量）；
（2）从顶点中选择一个顶点作为起始连通分量；
（3）选择与此连通分量连接的边中权值最小的边，加入连接的顶点且将此边加入到新图中，将此边舍去；
（4）重复步骤（3），直到所有顶点同时在一个连通分量上。
假设原连通带权图，起始点为A：
25 9 16 13 11 22 19 23 24 A B C D E F G根据此思想描述生成过程：
Prim Step 1 无边新图 25 9 16 13 11 22 19 23 24 A B C D E F G Prim Step 2 A为起始点 25 9 16 13 11 22 19 23 24 A B C D E F G Prim Step 3 AF有两条边 25 9 16 13 11 22 19 23 24 A B C D E F G Prim Step 4 AFE有3条边 25 9 16 13 11 22 19 23 24 A B C D E F G Prim Step 5 AFED有4条边 25 9 16 13 11 22 19 23 24 A B C D E F G Prim Step 6 AFEDC有4条边 25 9 16 13 11 22 19 23 24 A B C D E F G Prim Step 7 AFEDCB有4条边且AB有回路 25 9 16 13 11 22 19 23 24 A B C D E F G Prim 最终得到的最小生成树的图 25 9 16 13 11 22 19 23 24 A B C D E F G（1）首先，我们要获取顶点连接的边，还要知道它所连接的顶点，这需要一个数据结构：
// 边 typedef struct KruskalEdge { int first; // 第一个顶点下标 int second; // 第二个顶点下标 double weight; // 两顶点边的权值 KruskalEdge() : first(-1), second(-1), weight(0.0) { } } PrimEdge;（2）其次，我们需要挑选最小权值的边，这也可以使用多种排序方法实现；
（3）最后，我们要判断其边两顶点是否在不同的连通分量上 （按图的顶点） ，这和广度优先遍历一样，需要访问标记。
方式：
Kruskal通过边来构造最小生成树；Prim通过顶点来构造最小生成树；适用范围：
Kruskal对边稀疏与边稠密都适用；Prim仅对边稠密适用；复杂度（n个顶点，e条边，插入删除等使用小根堆O(log2e)）：
检测矩阵：邻接矩阵存储O(n2)，邻接表O(n±e)；Kruskal插入删除e次，则O(e log2e)；Prim需要O(n)次循环迭代，每次平均插入2e/n条边，e条边出堆，耗时O(e log2e)。插入，删除与排序，如果不想用内置方法，推荐使用小根堆，即插入：
// Author: https://blog.csdn.net/DarkRabbit // Minimum Spanning Tree // 小根堆插入，首下标从1开始 // params: // btTree: 堆树 // val: 插入的值 void BinaryInsertWithOne(std::vector<KruskalEdge>& btTree, KruskalEdge& val) { if (btTree.size() == 0) // 下标从1开始，最少要有一个元素 { btTree.push_back(KruskalEdge()); btTree.push_back(val); return; } int index = btTree.size(); // 插入后的下标 btTree.push_back(val); // 插入数值 int parent = index / 2; // 父结点下标 while (parent > 0 && btTree[index].weight < btTree[parent].weight) // 如果子结点小 { std::swap(btTree[index], btTree[parent]); // 交换父结点与当前结点 index = parent; // 重新设定下标 parent /= 2; // 重新计算父结点 } }