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

本文主要是介绍最小生成树 并查集 最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#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;//如果祖先结点的值不同说明不在一个集合中}elsereturn 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;
}

这篇关于最小生成树 并查集 最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---