union-find树结构代码,考虑路径压缩和秩启发式规则。
直接上源代码:
#include <stdio.h>
#include <malloc.h>
typedef struct Node
{
int name;//节点名
//int count;//以此节点为根的子节点数量
int father;//父亲节点
int rank;//秩
}TreeNode, *BiTree;
BiTree initializeNode(int num)
{
BiTree tn=(BiTree)malloc(num*sizeof(TreeNode));
for (int i=0;i<num;i++)
{
tn[i].name=i;
//tn[i].count=1;
tn[i].father=i;//父节点为自己
tn[i].rank=0;
}
return tn;
}
/************************************************************************
找到某个节点的根节点
输入参数:
root 根据节点名找到节点编号
tn:根据节点编号查询其父节点
name:节点名
输出参数:
index:根结点节点编号
************************************************************************/
int find(int *root,BiTree tn,int name){
int index=root[name];
BiTree t=&tn[index];
if (t->father!=index)
{
t->father=find(root,tn,tn[t->father].name);
}
return t->father;
}
//两个根结点合并
void f_union(int *root,BiTree bt,int name1,int name2,int re_name){
int index1=find(root,bt,name1);
int index2=find(root,bt,name2);
BiTree t1=&bt[index1];
BiTree t2=&bt[index2];
if (t1->rank>=t2->rank){
//如果T1的秩大,即T1的树高度高
t2->father=index1;
if (t1->rank==t2->rank){
t1->rank++;
}
if (re_name>=0)
{
t1->name=re_name;
root[re_name]=index1;
}
}
else{
t1->father=index2;
if (re_name>=0)
{
t2->name=re_name;
root[re_name]=index2;
}
}
}
void n_union(int *root,BiTree bt,int name1,int name2){
f_union(root,bt,name1,name2,-1);
}
void main()
{
int num=6;
BiTree tn=initializeNode(num);
int root[11]={-1};
for (int i=0;i<num;i++)
{
root[i]=i;
}
n_union(root,tn,1,2);
n_union(root,tn,3,4);
n_union(root,tn,4,5);
n_union(root,tn,4,2);
n_union(root,tn,2,0);
for (int i=0;i<num;i++)
{
printf("index:%d, ",i);
printf("name:%d, ",tn[i].name);
printf("rank:%d, ",tn[i].rank);
printf("father:%d\n",tn[i].father);
}
printf("root[name]:index\n");
for (int i=0;i<12;i++)
{
printf("root[%d]:%d\n",i,root[i]);
}
printf("\nprint end");
char ch = getchar();
}
分享到:
相关推荐
基于Union-Find数据结构实现Kruskal求最小生成树,代码设计及变量命名附详细注释。基于Union-Find数据结构实现Kruskal求最小生成树,代码设计及变量命名附详细注释。
并查集.并查集(Union-Find)是一种特殊的数据结构,它可以高效地管理一系列不交集的合并和查询操作。这种数据结构通常用树形结构来表示,并且常常在实际应用中以森林的形式存在。
∷相关函数:Find函数 Union函数 1.4.17 树的二叉链表存储的基本操作 193 范例1-71 树的二叉链表存储的基本操作 193 ∷相关函数:LevelOrderTraverse函数 1.4.18 二叉树的三叉链表存储的基本操作 201 范例1-72 ...
第2周-使用具有Union-Find结构的汉明距离的K聚类和隐式聚类 week3-背包问题动态算法 第4周-Floyd-Warshall全路径最短路径; 也是Cython版本 week5-旅行商问题动态规划算法 第6周-2-SAT问题简化为使用Kosaraju算法...
∷相关函数:Find函数 Union函数 1.4.17 树的二叉链表存储的基本操作 193 范例1-71 树的二叉链表存储的基本操作 193 ∷相关函数:LevelOrderTraverse函数 1.4.18 二叉树的三叉链表存储的基本操作 201 范例1-72 ...
带权并查集(Weighted Union-Find)是一种在数据结构中用于处理不相交集合(Disjoint Set)的算法,它通过合并过程来减少集合的数量,同时考虑合并操作的权重。以下是一个针对带权并查集模板的资源描述: 资源标题...
1.5 案例研究:union-find算法 136 1.5.1 动态连通性 136 1.5.2 实现 140 1.5.3 展望 148 第2章 排序 152 2.1 初级排序算法 153 2.1.1 游戏规则 153 2.1.2 选择排序 155 2.1.3 ...
并查集(Union-Find Set): 一种用于管理分组的数据结构。它具备两个操作:(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组。 注意:并查集不能将在同一组的元素拆分为两组。 并查集的实现: 用树来实现...
不相交集ADT8.1 等价关系8.2 动态等价性问题8.3 基本数据结构8.4 灵巧求并算法8.5 路径压缩8.6 按秩求并和路径压缩的最坏情形8.6.1 Union/Find算法分析8.7 一个应用总结练习参考文献第9章 图论算法9.1 若干定义9.1.1...
Kruskal 的数据结构:union-find 霍夫曼编码 分而治之的算法 递归的主定理 归并排序 O(n^{log_2(3)}) = O(n^{1.59})中两个 n 位因子的整数乘法 快速傅立叶变换 动态规划 记忆间隔调度 分段最小二乘法
∷相关函数:Find函数 Union函数 1.4.17 树的二叉链表存储的基本操作 193 范例1-71 树的二叉链表存储的基本操作 193 ∷相关函数:LevelOrderTraverse函数 1.4.18 二叉树的三叉链表存储的基本操作 201 范例1-72 ...
中的独立数据结构概述(union-find、trie 等)。 :常见的概率分布,PDF,CDF,模拟方法。 :通常有用但难以记住的 Python 技巧。 :高级张量流 API。 基本用例。 :更深入地研究特定的 ML 模型。 : 数据清洗、平滑...
并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。 顾名思义,并查集支持两种操作: 合并(Union):合并两个元素所属集合(合并对应的树...
∷相关函数:Find函数 Union函数 1.4.17 树的二叉链表存储的基本操作 193 范例1-71 树的二叉链表存储的基本操作 193 ∷相关函数:LevelOrderTraverse函数 1.4.18 二叉树的三叉链表存储的基本操作 201 范例1-72 ...
1.5 案例研究:union-find算法 136 1.5.1 动态连通性 136 1.5.2 实现 140 1.5.3 展望 148 第2章 排序 152 2.1 初级排序算法 153 2.1.1 游戏规则 153 2.1.2 选择排序 155 2.1.3 插入排序 ...
1.5 案例研究:union-find算法 136 1.5.1 动态连通性 136 1.5.2 实现 140 1.5.3 展望 148 第2章 排序 152 2.1 初级排序算法 153 2.1.1 游戏规则 153 2.1.2 选择排序 155 2.1.3 插入排序 157 2.1.4...
并查集(Disjoint-Set Union,简称DSU)是一种用于处理集合合并和查询问题的数据结构。它主要支持两种操作:查找(Find)和合并(Union)。并查集通常被用于解决一些图论、网络连接和集合类的算法问题。 ### 主要...
1.5 案例研究:union-find算法 1.5.1 动态连通性 1.5.2 实现 1.5.3 展望 第2章 排序 2.1 初级排序算法 2.1.1 游戏规则 2.1.2 选择排序 2.1.3 插入排序 2.1.4 排序算法的可视化 2.1.5 比较两种排序算法 ...