算法 - 图的实例 - 最小生成树 (Minimum Spanning Tree)
本文将介绍最小生成树的基础知识，并用C++实现克鲁斯卡尔算法(Kruskal)和普利姆算法(Prim)。
在查看本文之前，需要一些数据结构和程序语言的基础。
尤其是“矩阵”、“矩阵的压缩(matrix)”、“图(graph)”、“队列(queue)”等的知识。
文章目录
- 算法 - 图的实例 - 最小生成树 (Minimum Spanning Tree)
1 最小生成树简述 (Introduction)
-
对图使用不同的遍历方法，可得到不同的生成树；
-
从不同的顶点出发也能得到不通过的生成树。
-
有 n 个顶点的连通且带权的图由 n-1 条边；
-
最小生成树：
- 使用 n-1 条边连接网络中的 n 个顶点；
- 且不能使其产生回路；
- 各条边的权值总和最小。
-
重要结论：
- 当权值各边都不同时，最小生成树一定唯一；
- 当权值部分相同时：
- 邻接矩阵：由于选边顺序固定，则最小生成树唯一；
- 邻接表：由于边链表不唯一，则最小生成树不唯一。
2 克鲁斯卡尔算法 (Kruskal Algorithm)
2.1 算法基本思想 (Basic Idea)
-
（1）构造一个只有原连通带权图顶点的新图，即没有边只有顶点（每个顶点都是一个连通分量）；
-
（2）从原连通带权图所有边中选择权值最小的边，如果此边两顶点落在新图中不同的连通分量上，则将此边加入新图，将此边舍去；
-
（3）重复步骤（2），直到所有顶点同时在一个连通分量上。
假设原连通带权图：
根据此思想描述生成过程：
2.2 算法设计思路 (Design Idea)
-
（1）首先，我们要获取所有的边，还要知道它所连接的顶点，这需要一个数据结构：
// 边 typedef struct KruskalEdge { int first; // 第一个顶点下标 int second; // 第二个顶点下标 double weight; // 两顶点边的权值 KruskalEdge() : first(-1), second(-1), weight(0.0) { } } PrimEdge; -
（2）其次，我们需要挑选最小权值的边，这可以使用多种排序方法实现；
-
（3）最后，我们要判断其边两顶点是否在不同的连通分量上 （按图的边） ，这可以使用并查集来实现。
2.3 C++代码 (C++ Code)
-
（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; }
3 普利姆算法 (Prim Algorithm)
2.1 算法基本思想 (Basic Idea)
-
（1）构造一个只有原连通带权图顶点的新图，即没有边只有顶点（每个顶点都是一个连通分量）；
-
（2）从顶点中选择一个顶点作为起始连通分量；
-
（3）选择与此连通分量连接的边中权值最小的边，加入连接的顶点且将此边加入到新图中，将此边舍去；
-
（4）重复步骤（3），直到所有顶点同时在一个连通分量上。
假设原连通带权图，起始点为A：
根据此思想描述生成过程：
2.2 算法设计思路 (Design Idea)
-
（1）首先，我们要获取顶点连接的边，还要知道它所连接的顶点，这需要一个数据结构：
// 边 typedef struct KruskalEdge { int first; // 第一个顶点下标 int second; // 第二个顶点下标 double weight; // 两顶点边的权值 KruskalEdge() : first(-1), second(-1), weight(0.0) { } } PrimEdge; -
（2）其次，我们需要挑选最小权值的边，这也可以使用多种排序方法实现；
-
（3）最后，我们要判断其边两顶点是否在不同的连通分量上 （按图的顶点） ，这和广度优先遍历一样，需要访问标记。
2.3 C++代码 (C++ Code)
// Author: https://blog.csdn.net/DarkRabbit
// Minimum Spanning Tree
// 普利姆算法
// params:
// graph: 需要计算的图
// begin: 起始顶点
// paths: 输出的连接顺序
// return:
// AdjacencyMatrix<int>: 输出的最小生成树的图
AMGraphInt* Prim(AMGraphInt* graph, int begin, std::vector<PrimEdge>& paths)
{
if (graph == nullptr || graph->IsOriented()) // 如果是有序图返回
{
return nullptr;
}
int size = graph->GetVertexCount(); // 顶点数量
if (begin < 0 || begin >= size) // 起始点不在图中，直接返回
{
return nullptr;
}
AMGraphInt* minTree = CreateCopyVertexesGraph(graph); // 只复制顶点后的图
if (size <= 1) // 只有零到一个顶点
{
return minTree;
}
std::vector<bool> vertexMark = std::vector<bool>(size, false); // 顶点访问标记
std::queue<int> vertexes; // 顶点队列
std::vector<PrimEdge> edges; // 边
vertexes.push(begin); // 加入起始顶点
int index; // 当前顶点下标
while (!vertexes.empty())
{
index = vertexes.front();
vertexes.pop();
vertexMark[index] = true; // 访问过了
for (int adj = graph->FirstNeighbor(index);
adj != -1;
adj = graph->NextNeighbor(index, adj))
{
if (!vertexMark[adj]) // 如果邻接顶点没有找过边
{
PrimEdge edge;
edge.first = index;
edge.second = adj;
graph->TryGetWeight(index, adj, edge.weight);
edges.push_back(edge); // 加入边
}
}
if (!edges.empty())
{
std::sort(edges.begin(), edges.end(), [](PrimEdge& lhs, PrimEdge&rhs)->bool
{
return lhs.weight < rhs.weight;
}); // 从小到大
if (vertexMark[edges[0].second]) // 如果最小权值的边连接的顶点访问过了，证明所有顶点都访问过了
{
break;
}
else
{
minTree->TryPutWeight(edges[0].first, edges[0].second, edges[0].weight); // 设置边
minTree->TryPutWeight(edges[0].second, edges[0].first, edges[0].weight); // 设置边
paths.push_back(edges[0]); // 加入输出路径
vertexes.push(edges[0].second); // 将新连接的顶点加入节点队列
edges.erase(edges.begin()); // 取出最小边
}
}
}
return minTree;
}
4 两种算法的比较 (Comparing Two Algorithms)
-
方式：
- 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)。
5 主函数与测试 (Main Method and Testing)
插入，删除与排序，如果不想用内置方法，推荐使用小根堆，即插入：
// 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; // 重新计算父结点
}
}
5.1 主函数 (Main Method)
// Author: https://blog.csdn.net/DarkRabbit
// Minimum Spanning Tree
#include "abstract_graph.h"
#include "adjacency_matrix.h"
#include "minimum_spanning_tree.h"
#include <vector>
#include <unordered_map>
#include <iomanip>
#include <iostream>
using namespace std;
typedef Graphs::AMVertexNode<int> AMVertexInt;
typedef Graphs::AdjacencyMatrix<int> AMGraphInt;
void TestAdjacencyMatrix();
void TestKruskal();
void TestPrim();
int main()
{
//TestAdjacencyMatrix();
TestKruskal();
TestPrim();
system("pause");
return 0;
}
// 打印邻接矩阵
template<class TGraph>
void PrintMatrix(TGraph& graph);
// 克鲁斯卡尔 Kruskal
void TestKruskal()
{
AMGraphInt* graph = new AMGraphInt({ 0, 1, 2, 3, 4, 5, 6 }, false); // 无向图 0-6
graph->InitializeWeights(
{ {0, 1}, {0, 5}, {1, 2}, {1, 6}, {2, 3}, {3, 4}, {3, 6}, {4, 5}, {4, 6} },
{ 25, 9, 16, 13, 11, 22, 19, 23, 24 }); // 初始化边
vector<Graphs::MinimumSpanningTree::KruskalEdge> edges;
AMGraphInt* minTree = Graphs::MinimumSpanningTree::Kruskal(graph, edges);
cout << "----------克鲁斯卡尔 Kruskal----------" << endl;
cout << "无向图：" << endl;
cout << "邻接矩阵：" << endl;
PrintMatrix(*graph);
cout << endl;
cout << "克鲁斯卡尔最小生成树的图：" << endl;
PrintMatrix(*minTree);
cout << endl;
cout << "生成边顺序为：" << endl;
for (int i = 0; i < edges.size(); i++)
{
cout << (char)(edges[i].second + 'A');
cout << " ---" << edges[i].weight << "--- ";
cout << (char)(edges[i].first + 'A') << endl;
}
cout << "--------------------" << endl;
delete graph;
delete minTree;
cout << endl;
}
// 普利姆 Prim
void TestPrim()
{
AMGraphInt* graph = new AMGraphInt({ 0, 1, 2, 3, 4, 5, 6 }, false); // 无向图 0-6
graph->InitializeWeights(
{ {0, 1}, {0, 5}, {1, 2}, {1, 6}, {2, 3}, {3, 4}, {3, 6}, {4, 5}, {4, 6} },
{ 25, 9, 16, 13, 11, 22, 19, 23, 24 }); // 初始化边
vector<Graphs::MinimumSpanningTree::PrimEdge> edges;
AMGraphInt* minTree = Graphs::MinimumSpanningTree::Prim(graph, 0, edges);
cout << "----------普利姆 Prim----------" << endl;
cout << "无向图：" << endl;
cout << "邻接矩阵：" << endl;
PrintMatrix(*graph);
cout << endl;
cout << "普利姆最小生成树的图：" << endl;
PrintMatrix(*minTree);
cout << endl;
cout << "生成边顺序为：" << endl;
for (int i = 0; i < edges.size(); i++)
{
cout << (char)(edges[i].first + 'A');
cout << " ---" << edges[i].weight << "--- ";
cout << (char)(edges[i].second + 'A') << endl;
}
cout << "--------------------" << endl;
delete graph;
delete minTree;
cout << endl;
}
5.2 打印结果 (Print Output)
----------克鲁斯卡尔 Kruskal----------
无向图：
邻接矩阵：
A B C D E F G
A 0 25 0 0 0 9 0
B 25 0 16 0 0 0 13
C 0 16 0 11 0 0 0
D 0 0 11 0 22 0 19
E 0 0 0 22 0 23 24
F 9 0 0 0 23 0 0
G 0 13 0 19 24 0 0
克鲁斯卡尔最小生成树的图：
A B C D E F G
A 0 0 0 0 0 9 0
B 0 0 16 0 0 0 13
C 0 16 0 11 0 0 0
D 0 0 11 0 22 0 0
E 0 0 0 22 0 23 0
F 9 0 0 0 23 0 0
G 0 13 0 0 0 0 0
生成边顺序为：
A ---9--- F
C ---11--- D
B ---13--- G
B ---16--- C
D ---22--- E
E ---23--- F
--------------------
----------普利姆 Prim----------
无向图：
邻接矩阵：
A B C D E F G
A 0 25 0 0 0 9 0
B 25 0 16 0 0 0 13
C 0 16 0 11 0 0 0
D 0 0 11 0 22 0 19
E 0 0 0 22 0 23 24
F 9 0 0 0 23 0 0
G 0 13 0 19 24 0 0
普利姆最小生成树的图：
A B C D E F G
A 0 0 0 0 0 9 0
B 0 0 16 0 0 0 13
C 0 16 0 11 0 0 0
D 0 0 11 0 22 0 0
E 0 0 0 22 0 23 0
F 9 0 0 0 23 0 0
G 0 13 0 0 0 0 0
生成边顺序为：
A ---9--- F
F ---23--- E
E ---22--- D
D ---11--- C
C ---16--- B
B ---13--- G
--------------------
请按任意键继续. . .