最小生成树 并查集 最短路径

#include<stdio.h>
#include<stdlib.h>
struct edge{
int u;
int v;
int w;//为了方便排序这里穿件一个结构体来存储边的关系
}e[10];
int n,m;
int f[10]={0},sum=0,count=0;//并查集需要得到的一些变量
//f数组大小根据实际情况来设置，要比n的最大值大1

//排序
int cmp(const void *a,const void *b)
{
 return (((struct edge *)a)->w-((struct edge *)b)->w);
}

int getf(int u)
{
	if(f[u]==u)
		return u;
	else
	{
		f[u]=getf(f[u]);
	     return f[u];
	}
}

int merge(int u,int v)
{
	int t1,t2;
	t1=getf(u);//寻找祖先结点
	t2=getf(v);//寻找祖先结点
	if(t1!=t2)//判断两个点是否在同一个集合中
	{
		f[t2]=t1;
		return 1;//如果祖先结点的值不同说明不在一个集合中
	}
	else
		return 0;//相同 在一个集合中
}

int main()
{
	int i;
	//读入n和m，n表示顶点个数， m表示边的条数
	scanf("%d%d",&n,&m);

	//读入边，这里用一个结构体来存储边的关系
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	qsort(e,m+1,sizeof(e[0]),cmp);
	//并查集初始化
	for(i=1;i<=n;i++)
	{
		f[i]=i;
	}
	//kruskal算法核心部分
	for(i=1;i<=m;i++)
	{
		if(merge(e[i].u,e[i].v)==1)//两个点不在一个集合中
		{
			count++;//加上边的个数
		  sum=sum+e[i].w;//计算最小的和
		}
		if(count==n-1)//知道选用了n-1跳变之后退出循环
			break;
	}
	for(i=1;i<=m;i++)
	{
		printf("%d %d %d\n",e[i].u,e[i].v,e[i].w);
	}
	printf("%d\n",sum);//输出最小路径
	return 0;
}

最小生成树 并查集 最短路径

原文：http://blog.csdn.net/u013238646/article/details/45336391