[数据结构与算法]C/C++图的最小生成树

先看一下这个带权值的无向图

现在要求用最少的边（权值和）让整个图连通，也就是任意两点都可互相访问到，因为不包含回路的连通无向图就是一棵树，所以就是来求最小生成树。
一提到求最小，我们很容易就想起了贪心算法，就是先把各边的按权值从小到大排列，然后每次只要最小的，最后就能保证结果就是最小的。
但是约束条件是什么呢？比如如何判断最后是否是个连通图，如何判断两点连通，这时候就要知道两个很重要的特性：
1.n个顶点的连通图，至少要n-1条边！！！所以最小连通图为n-1条边
2.2个点连通，则其为同一祖先
判断是否同一祖先，可以用并查集；由于边是按权值从小到大排列的，所以只要依次找n-1条符合条件的边，即可满足连通图的特性

//核心代码
	for(int i=0;i<m;i++)
	{
		if(compare(a[i].u,a[i].v))//是否同一祖先
		{
			flag++;
			sum=sum+a[i].w;
			cout<<"第"<<flag<<"条边是：";
			cout<<a[i].u<<" "<<a[i].v<<endl;
		}
		if(flag==n-1)//n-1条边代表已经图已经连通
		{
			cout<<"最短路径为："<<sum;
			break;
		}
	}

并查集两个函数

int seek(int x)
{
	if(f[x]==x) return x;
	else
	{
		f[x]=seek(f[x]);
		return f[x];
	}
}

int compare(int x,int y)
{
	int t1,t2;
	t1=seek(x);
	t2=seek(y);
	if(t1!=t2)
	{
		f[t2]=t1;
		return 1;
	}
	else return 0;
}

完整代码如下

#include <iostream>
#include <bits/stdc++.h>
using  namespace std;
int f[100];
//此处用结构体，方便
struct node{
	int u;
	int v;
	int w;
};
bool cmp(node x,node y)
{
	return x.w<y.w;
}
int seek(int x)
{
	if(f[x]==x) return x;
	else
	{
		f[x]=seek(f[x]);
		return f[x];
	}
}
int compare(int x,int y)
{
	int t1,t2;
	t1=seek(x);
	t2=seek(y);
	if(t1!=t2)
	{
		f[t2]=t1;
		return 1;
	}
	else return 0;
}
int main()
{
	vector <node> a;
	int n,m,flag=0,sum=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		{
			f[i]=i;
		}
	for(int i=1;i<=m;i++)
	{
		node t;
		cin>>t.u>>t.v>>t.w;
		a.push_back(t);
	}
	sort(a.begin(),a.end(),cmp);
	for(int i=0;i<m;i++)
	{
		if(compare(a[i].u,a[i].v))
		{
			flag++;
			sum=sum+a[i].w;
			cout<<"第"<<flag<<"条边是：";
			cout<<a[i].u<<" "<<a[i].v<<endl;
		}
		if(flag==n-1)
		{
			cout<<"最短路径为："<<sum;
			break;
		}
	}
	return 0;
}

样例
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
运行结果