代码示例👇

//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.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算法更适用于稀疏图。