首页 > 代码库 > 克鲁斯卡尔算法+并查集
克鲁斯卡尔算法+并查集
算法要点：Kruskal算法的最难点在于怎样判断加入边(x,y)后是否形成了环。
问题可化为：判断边(x,y)的两个顶点x,y在图（实际是森林）mst中最否已经连通。如果已经连通，加入边将形成环；否则，不形成环。
在kruskal算法中，要用到并查集的合并和查找
并查集：
1 int getfa(int k) //找到最祖先 2 { 3 if(fa[k]==k) return k; 4 fa[k]=getfa(fa[k]); 5 return fa[k]; 6 } 7 8 void merge(int x,int y) //合并祖先 9 {10 int fx=getfa(x);11 int fy=getfa(y);12 fa[fx]=fy;13 }14 15 bool judge(int x, int y) //判断是不是一个祖先16 {17 int fx=getfa(x);18 int fy=getfa(y);19 return fx==fy;20 }
kruskal算法核心：
1 for(int i=1;i<=n;i++) 2 fa[i]=i; 3 sort(e+1,e+1+len,mys); 4 int cal=0; 5 for(int i=1;i<=len;i++) 6 { 7 int v=getfa(e[i].x); 8 int u=getfa(e[i].y); 9 if(v!=u)10 {11 merge(v,u);12 //根据题意添加13 if(++cal==n-1)14 {15 break;16 }17 }18 }
输入：
1 int fa[maxn]; 2 int len=0; 3 struct node 4 { 5 int x,y,v; 6 }e[maxn]; 7 8 void init(int xx,int yy,int vv) 9 {10 if(yy<0||yy>n*m) return;11 e[++len].y=yy;12 e[len].x=xx;e[len].v=vv;13 }14 15 int main()16 {17 memset(e,0,sizeof(e));18 cin>>n>>m;19 for(int i=1;i<=m;i++)20 {21 int xx,yy,vv;22 cin>>xx>>yy>>vv;23 init(xx,yy,vv);24 init(yy,xx,vv);25 }
克鲁斯卡尔算法+并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。