数据结构：最小生成树算法模板prim和kruskal（考研）

#include <iostream>
#include <cstring>
#include <algorihtm>
using namespace std;

const int N=510;
const int INF=0x3f3f3f3f;
int dist[N];//保存距离
bool st[N];//标记点是否已经被访问过
int g[N][N];//邻接矩阵存储图

int n, m;

//返回值为最小生成树的权值
int prim() { 
	memset(dist, INF, sizeof(dist));
	int res = 0;
	for(int i=0; i<n; ++i) {
		int t = -1;
		//寻找当前权值最小的边    并将其所连接的边并入的MST中
		for(int j=1; j<=n; ++j) {
			//这里包含了两种情况   
			//（1）初始状态t==-1  （2）其他边的权值更小并且所连接的点没有被访问过  
			if(!st[j] && (t==-1  || dist[j] < dist[t]) 
				t = j;
		}
		if(i && dist[t]==INF) return INF;
		if(i) res += dist[t];// 因为t==0的时候res=0 不需要你进行相加
		st[t] = true;//标记访问过了

		//以t顶点作为媒介  更新侯选边的权值
		for(int j=1; j<=n; ++j) dist[j] = min(dist[j], g[t][j]);
	}
	return res;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int N=510;
const int M=1000;
const int INF=0x3f3f3f3f;

int father[N];

int find(int x) {
	int a = x;
	while(x != father[x]) x = father[x];
	while(a != father[a]) {
		int z = a;
		father[z] = x;
		a = father[a];
	}
	return x;
}

void Union(int a, int b) {
	int fa = find(a);
	int fb = find(b);
	if(fa != fb) father[fa] = fb;
}

//边类
struct Edge{
	int a, b;
	int weight;
}edges[M];


//返回值为MST的权值
int kruskal() {
	int res = 0;
	int cnt = 0;
	sort(edges, edges+m, [](const Edge &a, const Edge& b) {return a.weight < b.weight;});
	for(int i=1; i<=n; ++i) father[i] = i;//初始化并查集数组
	
	//遍历边集   已经按照权值由小到大排好序了
	for(int i=0; i<m; ++i) {
		int a = edges[i].a;
		int b = edges[i].b;
		
		//为了保证添加进去edges[i]这条边后不形成回路
		//所以首先要判断这条边的两个顶点是否在 不同的连通分量中
		if(find(a) != find(b)) {
			//证明两个顶点在不同的连通分量中
			res += edges[i].weight;
			Union(a, b);
			cnt ++;
		}
	}
	//如果最后得到的MST的边数 小于 n-1 证明不是最小生成树
	if(cnt < n-1) return INF;
	return res;
}