克鲁斯卡尔算法是怎样判断是否构成了回路

克鲁斯卡尔算法 判断回路中的问题~

看这段代码真令我头疼，我就告诉你思路吧！
并查集你会不会？如果会的话那就好办。
kruskal算法用到了一种贪心策略，首先要把边集数组以边的权值从小到大排序，然后一条边一条边的查找，如果边的两个端点不在一个集合内，则将此边添加到正在生长的树林中，并合并两个端点所在的集合，直到最小生成树已生成完毕。
核心伪代码如下（本人不习惯给完整的可编译的代码）：
func root(x:longint):longint;//查找i节点所在集合
var i,j,k:longint;
{i:=x;j:=x;
while i!=f[i] do i=f[i];
while j!=i do
{k=j;j=f[j];f[k]=i;}//路径压缩，若不压缩效率将很低
};//root
proc union(i,j,c:longint);
var x,y:longint;
{x=root(i);
y=root(j);
if x!=y then {inc(ans,c);inc(temp);f[y]=x;}
//若i和j分属两棵子树，则将此边添加到森林中，并合并其所在集合
};//union;
将边集数组按照边的权值从小到大排序;
for (i=1,i++,i=n) f[i]=i;//并查集初始化
for (i=1,i++,i=m)
{union(edge[i].x,edge[i].y,edge[i].z);
if temp==n-1 then break;
//若temp==n-1则最小生成树已生成完毕，退出
}//kruskal
if temp==n-1 then writeln(ans)//输出最小生成树的权值和
else writeln('No solution!');//若temp!=n-1，则说明此图为非连通图

如果你想要加入的那条边，它的两个顶点的祖先是同一个， 你加进去就会有回路

使用遍历方法，同时存储他们的父亲节点，如果父亲节点不一样，就说明有回路

以下给出并查集实现的克鲁斯卡尔算法，求解生成网络的最小费用，并输出生成网络里的路径。
#include<iostream>
#include<algorithm>
using namespace std;
int p[1001],rank[1001];
int cho[1001];
struct edge
{
int u,v,w;//u表示起始点编号，v表示终点编号，w表示该路径费用
}e[15001];
int n,m;//n表示点的个数，m表示路径数
void Init()
{
int i;
for(i=1;i<=n;i++)
{
p[i]=i;
rank[i]=0;
}
}
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int Find(int t)
{
if(p[t]!=t)
{
p[t]=Find(p[t]);
}
return p[t];
}
int Union(int a,int b)
{
int x,y;
x=Find(a);
y=Find(b);
if(rank[x]>rank[y])
{
p[y]=x;
}
else
{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
Init();
sort(e,e+m,cmp);
int cnt=0,ans=0;
for(i=0;i<m;i++)
{
if(Find(e[i].u)!=Find(e[i].v))
{
cnt++;
ans+=e[i].w;
Union(e[i].u,e[i].v);
cho[++cho[0]]=i;
if(cnt==n-1)
break;
}
}
printf("%d\n",ans);
for(j=1;j<=cho[0];j++)
{
printf("%d %d\n",e[cho[j]].u,e[cho[j]].v);
}
return 0;
}

---

渑池县17679442197： 克鲁斯卡尔算法是怎样判断是否构成了回路 - ？
路全威乐： 使用遍历方法,同时存储他们的父亲节点,如果父亲节点不一样,就说明有回路

渑池县17679442197： C语言 克鲁斯卡尔算法怎么判断是否构造成回路?求大手解答 - ？
路全威乐： 使用并查集,每个讲克鲁斯卡尔的算法都会涉及并查集. 初始为每个顶点属于互不相同的集合,当添加一条边时,就把这两条边的顶点加入到同一集合.如果边的两顶点属于不同集合,就可以添加这条边,否则就不可以添加(会构成回路). 对于集合的操作,有子集的划分.前几天的天津还是哪个regional网络预赛,就有个子集划分的题目.

渑池县17679442197： 有关克鲁斯卡尔算法 - ？
路全威乐： 可以用并查集,一开始每个点自己是一个集合,判断一条边时,如果发现他们在并查集中的祖先相同,则会构成回路,否则不会.把这条边加入时,只要把他们的祖先并起来就可以了.查找祖先的时候可以顺便压缩一下路径,每次均摊时间复杂度O(1). 具体实现可以参考有关并查集的内容.

渑池县17679442197： 克鲁斯卡尔算法的介绍 - ？
路全威乐： 克鲁斯卡尔算法是在剩下的所有未选取的边中,找最小边,如果和已选取的边构成回路,则放弃,选取次小边.

渑池县17679442197： 生成最小生成树Kruskal算法中,如何判定是否存在回路? - ？
路全威乐： 如果你想要加入的那条边,它的两个顶点的祖先是同一个, 你加进去就会有回路

渑池县17679442197： 克鲁斯卡尔算法 判断回路中的问题 - ？
路全威乐： 看这段代码真令我头疼,我就告诉你思路吧!并查集你会不会?如果会的话那就好办.kruskal算法用到了一种贪心策略,首先要把边集数组以边的权值从小到大排序,然后一条边一条边的查找,如果边的两个端点不在一个集合内,则将此边添加...

渑池县17679442197： 求一个学过数据结构(C语言版)的大神,有一个关于克鲁斯卡尔算法和普里姆算法的问题! - ？
路全威乐： 其实这个parent 数组就是用来判断新选择的边是否和现有的边构成环路 这个结构就是一个树的双亲表示,当新边的两个顶点所在的树根不是同一个时,自然就是表示加入这两个顶点间的边不够成环路 这种结构通称“并查集”,用来检测等价关系的,这里用来判断顶点是否在一个集合中,可以看比较全面的《数据结构》教材树那个一章的介绍

渑池县17679442197： 数据结构什么是最小生成树?有几种方式构造 - ？
路全威乐： 普里姆算法的基本思想:取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w.在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小.之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止. 克鲁斯卡尔算法 克鲁斯卡尔算法的基本思想:为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小. 具体做法: 先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止.

渑池县17679442197： 克鲁斯卡尔时间复杂度怎么算出来的 - ？
路全威乐： Kruskal算法的时间复杂度由排序算法决定,若采用快排则时间复杂度为O(N log N).kruskal算法:求加权连通图的最小生成树的算法.kruskal算法总共选择n- 1条边,(共n个点)所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的 ...

渑池县17679442197： 普里姆算法到底是怎么算的? - ？
路全威乐： )生成树一个连通图的生成树是它的极小连通子图,在n个顶点的情形下,有n-1条边.生成树是对连通图而言的,是连通图的极小连通子图,包含图中的所有顶点,有且仅有n-1条边.非连通图的生成树则组成一个生成森林;若图中有n个顶点,...