Kruskal算法

Kruskal算法是一种用于在无向加权图中找到最小生成树的算法。Kruskal算法基于贪心策略，通过不断选择当前权值最小的边，同时保证加入这条边后不会形成环，来逐步构建最小生成树。

下述代码使用了并查集，方便高效地判断图中的顶点是否属于同一个集合（即是否连通），从而避免形成环。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10,inf = 0x3f3f3f3f;
struct edge    
{
	int s,e;	//边的顶点和终点
	int w;	//边的权重
	bool operator < (const edge &a)  //重写
	{
		return w<a.w;
	}
};
edge temp[maxn]; 
int n,m;
//并查集相关代码
int p[maxn];
int find(int x)
{
	if(p[x]!=x)		p[x] = find(p[x]);
	return p[x];
}
void unite(int x,int y)
{
	p[find(x)] = find(y);
}

int kruskal()
{
	sort(temp,temp+m);
	for(int i =0;i<n;i++)
	p[i] = i;
	int res=0;
	for(int i =0;i<m;i++)
	{
		edge e = temp[i];
		if(!(find(e.s)==find(e.e)))
		{
			unite(e.s,e.e);
			res+=e.w;	
		}
	}
	return res;
}

int main()
{
	cin>>n>>m;
	for(int i =0;i<m;i++)
	{
		int s,e,w;
		cin>>s>>e>>w;
		temp[i].s = s;temp[i].e = e;temp[i].w = w; 
	}
	cout<<kruskal()<<endl;
	return 0;
}

Prim算法

Prim算法是另一种用于在无向加权图中找到最小生成树的算法。与Kruskal算法不同，Prim算法从图的某一个顶点开始，逐步增加边和顶点，直到形成最小生成树。Prim算法也基于贪心策略，但它关注的是从已选择的顶点集合中向外扩展，选择连接已选择顶点集合与未选择顶点集合中，且权值最小的边。

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1000,INF = 0x3f3f3f3f;
int g[MAXN][MAXN],dist[MAXN],n,m,res;
bool book[MAXN];
void prim()
{
	dist[1] = 0;
	book[1] = true;
	for(int i = 2;i<=n;i++)
		dist[i] = min(dist[i], g[1][i]);
	for(int i =2;i<=n;i++)
	{
                /*
		for(int j = 1;j<=n;j++)
		cout<<  dist[j]<<' ';
		cout<<endl;
                */
		int temp = INF;		//距离初始化 
		int t = -1;		//寻找最近的点加入集合中，用t来记录下标 
		for(int j = 2; j<=n; j++)
		{
			if(!book[j]&&dist[j]<temp)	//点未加入集合，距离小于temp就将下标赋给t
			{
				temp = dist[j];		//更新最小值 
				t = j;	
			}	
		}
		//cout<<t<<endl;
		if(t == -1)
		{
			res = INF;	
			return ;
			//如果t = -1，那么集合中找不到，生成树构建失败 
		}
		book[t] = true;
		res+=dist[t];
		for(int j = 2;j<=n;j++)
			dist[j] = min(dist[j], g[t][j]);
		
	}
}

int main()
{
	cin>>n>>m;	//n是点数，m是边数 
	memset(g, INF,sizeof g);	//任意两点间距离是INF 
	memset(dist, INF, sizeof dist); 	//所有点到集合S的距离是INF
	for(int i = 1;i<=m;i++)
	{
		int a,b,w;
		cin>>a>>b>>w;
		g[a][b] = g[b][a] = w;
	} 
	prim();
	if(res == INF)
		cout<<-1<<endl;
	else
		cout<<res<<endl;
	return 0;
} 

/*
7 12
1 2 23
1 7 36
1 6 28
6 7 25
2 7 1
6 5 17
2 3 20
3 4 15
7 4 9
7 5 16
5 4 3
7 3 4
*/