最小生成数(并查集)Kruskal算法

简介: 并查集:使用并查集可以把每个连通分量看作一个集合,该集合包含连通分量的所有点。这两两连通而具体的连通方式无关紧要,就好比集合中的元素没有先后顺序之分,只有属于和不属于的区别。#define N 100 int father[N]; void init() { for(int i=0;i
并查集:
使用并查集可以把每个连通分量看作一个集合,该集合包含连通分量的所有点。这两两连通而具体的连通方式无关紧要,
就好比集合中的元素没有先后顺序之分,只有属于和不属于的区别。
#define N 100 int father[N]; void init() { for(int i=0;i<n;i++) father[i]=1; } void union(int x,int y) //合并两元素所在集合 { x=getfather(x); y=getfather(y); if(x!=y) father[x]=y; } /*bool same(int x,int y) //判断两元素在不在同一集合 {return getfather(x)==getfather(y);} */ int getfather(int x) //获得该元素的父亲节点 { while(x!=father[x]) {x=father[x];} return x; }

 

相关文章
|
4月前
|
算法 搜索推荐
Kruskal算法
Kruskal算法
|
5月前
|
算法 C++
用prim和kruskal算法求最小生成树问题
用prim和kruskal算法求最小生成树问题
47 0
|
8月前
|
存储 算法 C++
最小生成树问题及Kruskal算法的解析
最小生成树问题及Kruskal算法的解析
73 2
|
10月前
|
算法 Java
数据结构(13)最小生成树JAVA版:prim算法、kruskal算法
13.1.概述 最小生成树,包含图的所有顶点的一棵树,树的边采用包含在图中的原有边中权重和最小的边。翻译成人话就是遍历一遍全图所有顶点的最短路径,这条路径就叫最小生成树。 最小生成树存在和图是连通图互为充要条件,顶点都不连通,肯定不可能有路能遍历一遍全图。 求解最小生成树有两种常用算法:
108 0
|
10月前
|
算法 Java 内存技术
Kruskal算法求最小生成树 Java带输入输出
Kruskal算法求最小生成树 Java带输入输出
74 0
|
10月前
|
算法
Prim算法和Kruskal算法到底哪个好?
Prim算法和Kruskal算法到底哪个好?
136 0
|
10月前
|
算法
LeetCode算法小抄 -- Kruskal 最小生成树算法
LeetCode算法小抄 -- Kruskal 最小生成树算法
|
11月前
|
算法
大话数据结构--Kruskal算法
大话数据结构--Kruskal算法
63 0
|
11月前
|
算法 内存技术
搜索与图论-最小生成树(Prim 算法和 Kruskal 算法)
搜索与图论-最小生成树(Prim 算法和 Kruskal 算法)
kruskal算法的实现
kruskal算法的实现