代码示例👇
//author:Mitchell_Donovan//date:5.11#include<iostream>#include<queue>#include<iomanip>//用于保留两位小数输出using namespace std;//边类class Edge {public:int from, to;double weight;Edge() {from = -1;to = -1;weight = 0;}Edge(int fromValue, int toValue, double weightValue) {from = fromValue;to = toValue;weight = weightValue;}};//图类class Graph {public:int numVertex;int numEdge;int* Mark;//标记图中顶点是否被访问过int* Indegree;//存放图中顶点的入度Graph(int num) {numVertex = num;numEdge = 0;Indegree = new int[numVertex];Mark = new int[numVertex];for (int i = 0; i < numVertex; i++) {Mark[i] = 0;//0表示未访问过Indegree[i] = 0;//入度设为0}}~Graph() {delete[]Mark;delete[]Indegree;}//判断是否为边bool isEdge(Edge oneEdge) {if (oneEdge.weight > 0 && oneEdge.weight < INFINITY && oneEdge.to >= 0) {return true;}else {return false;}}//访问void Visit(Graph& G, int v) {cout << v + 1 << " ";//cout << G.data[v];}};//用相邻矩阵表示图class Graphm :public Graph {//类继承private:double** matrix;//指向相邻矩阵的指针public:Graphm(int num) :Graph(num) {matrix = (double**)new double* [numVertex];//申请二维数组空间for (int i = 0; i < numVertex; i++) {matrix[i] = new double[numVertex];}for (int i = 0; i < numVertex; i++) {//相邻矩阵初始化for (int j = 0; j < numVertex; j++) {matrix[i][j] = 0;}}}~Graphm() {for (int i = 0; i < numVertex; i++) {delete[]matrix[i];}delete[] matrix;}//返回顶点的第一条边Edge firstEdge(int oneVertex) {Edge myEdge;myEdge.from = oneVertex;for (int i = 0; i < numVertex; i++) {if (matrix[oneVertex][i] != 0) {myEdge.to = i;myEdge.weight = matrix[oneVertex][i];break;}}return myEdge;}//返回与已知边相同顶点的下一条边Edge nextEdge(Edge preEdge) {Edge myEdge;myEdge.from = preEdge.from;if (preEdge.to >= numVertex) {//不存在下一条边return myEdge;}for (int i = preEdge.to + 1; i < numVertex; i++) {if (matrix[preEdge.from][i] != 0) {myEdge.to = i;myEdge.weight = matrix[preEdge.from][i];break;}}return myEdge;}//为图设置一条边void setEdge(int from, int to, double weight) {if (matrix[from][to] <= 0) {//如果原边不存在numEdge++;Indegree[to]++;}matrix[from][to] = weight;}//删除图的一条边void delEdge(int from, int to) {if (matrix[from][to] > 0) {//如果原边存在numEdge--;Indegree[to]--;}matrix[from][to] = 0;}};//等价类定义class ParTree {private:int* index;int size;public:ParTree(int sizeValue) {size = sizeValue;index = new int[size];for (int i = 0; i < size; i++) {index[i] = i;}}~ParTree() {delete[]index;index = NULL;}bool Different(int x, int y) {return index[x] != index[y];}void Union(int x, int y) {int m = index[y];for (int i = 0; i < size; i++) {if (index[i] == m) {index[i] = index[x];}}}};//最小生成树void Kruskal(Graphm& G) {ParTree A(G.numVertex);//等价类struct cmp {bool operator ()(const Edge& a, const Edge& b) {return a.weight > b.weight;}};priority_queue<Edge, vector<Edge>, cmp> minHeap;//最小堆Edge* MST = new Edge[G.numVertex - 1];//数组MST用于保存最小生成树的边int MSTtag = 0;//最小生成树的边计数for (int i = 0; i < G.numVertex; i++) {//将图的所有边插入最小堆中for (Edge e = G.firstEdge(i); G.isEdge(e); e = G.nextEdge(e)) {if (e.to > e.from) {//对于无向图，防止重复插入边minHeap.push(e);}}}int EquNum = G.numVertex;//开始时每个顶点分别为一个等价类Edge e;while (EquNum > 1) {if (!minHeap.empty()) {e = minHeap.top();//获得权值最小的一条边minHeap.pop();}if (minHeap.empty() || e.weight == INFINITY) {cout << "不存在最小生成树！";delete[] MST;MST = NULL;return;}if (A.Different(e.from, e.to)) {A.Union(e.from, e.to);EquNum--;cout << e.from << "->" << e.to << endl;}}cout << "成功！";}int main() {int n, m;cout << "顶点个数：";cin >> n;Graphm test(n);cout << "图中边的个数：";cin >> m;int from, to;double weight;for (int i = 0; i < m; i++) {cout << "第" << i + 1 << "条边的起点、终点、权重：";cin >> from;cin >> to;cin >> weight;test.setEdge(from, to, weight);test.setEdge(to, from, weight);}cout << "开始构造最小生成树：" << endl;Kruskal(test);}
输入示例👇
顶点个数：7
图中边的个数：9
第1条边的起点、终点、权重：0 4 1
第2条边的起点、终点、权重：0 1 20
第3条边的起点、终点、权重：1 3 4
第4条边的起点、终点、权重：1 2 6
第5条边的起点、终点、权重：4 5 15
第6条边的起点、终点、权重：3 5 12
第7条边的起点、终点、权重：2 6 2
第8条边的起点、终点、权重：3 6 8
第9条边的起点、终点、权重：5 6 10
输出示例👇
补充说明
Kruskal算法的时间复杂度主要取决于边数，因此Kruskal算法更适用于稀疏图。
