注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

最小生成树----Kruskal算法(草稿)  

2012-10-15 20:11:00|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最小生成树的概念就不讲了。直接讲实现,实现最小生成树的算法一般有两种。一种Kruskal算法,还有一种prim算法。先讲Kruskal算法。
其实Kruskal算法的主要思想是尽可能的选取短边作为生成树的边。

实现方法的分析
(1.生成树的存储方式
结点可有三个元素组成:V1,V2,e。V1,V2分别代表两边的端点,e代表V1,V2间的长度。
(2.图的边集的存储方式
优先队。(能适应查找,删除,插入,求最小元素的数据结构)一般有 检索树,平衡树,堆。
优先队的特点是可以方便的反复找出并删除当前的最小的元素。
只要求删除当前最小的元素,例如本算法中图的边集,这种情况下,堆是一种很好的优先队的结构。
(3.如何判断回路
我们可以想象,若v,w原先就已经连通,在这种情况下在加端点为v,w的边时,会构成回路,因而可以将判断回路转变为判断是否 连通。
(4.如何判断是否连通
这时候,我们可以这样思考,将所有已经相互连通的顶点放在同一集合内。即,若v,w在同一集合内,它们已经连通,反之,则没 有连通。
具体做法:
<1.开始时,每个顶点自成一个子集。
<2.每当选出一条最短边(v,w)的时候,判断它们是否已经在同一集合。
<3.若已经在同一集合,那么就舍弃这条边。
<4.若不在一个集合,那么选中这条边,将这条边放到生成树的边集中去。同时合并v所在的顶点子集和w所在的顶点子集。

伪代码:
void Kruskal()
{
int e = 0; //记录边数
每个顶点自成一格集合,并指定集合名。
while(t < n - 1) //n为结点数
{
从G中选出当前最短边(v,w);
找到v所在集合的集合名i,找到w所在集合的集合名j; //语句a;
if(i != j)
{
将(v,w)加入树边集;
e++;
合并i和j集合; //语句b;
}
}
}

实现语句a和语句b可以用union-find算法。
union-find算法:(并查集)
union-find算法处理对象特点:
(1.n个元素分别是或者可以编号0~n-1的整数。
(2.开始时元素自成一个集合,到最后合并成一个集合族。
(3.对集合族中的集合反复执行union(a,b,c)和s = find(i)运算。分别为将a和b所在的集合合并成c集合,求元素i所在的集合名。
union-find树:
用树表示集合,每个集合对应一棵树。
用父亲链接法来建树。用数组father[n]存储整个森林,数组元素作为元素值。若结点j是结点 i 的父亲,那么father[ i ] = j;若j是· 根,则father[ j ] = j;


//union-find算法

typedef struct
{
int father,name,count;

}nfNode;

void InitNF(nfNode nf[],int root[])
{
for(int i = 0;i < n;i++)
{
nf[i].name = nf[i].father = root[i] = i;
nf[i].count = 1;
}
}

//查找元素i所在的集合名
int find(int i,ufNode nf[])
{
int j = i;
while(nf[j].father != j) j = nf[j].father;
int a = nf[j].name;
int x = i;
int y;
while(nf[x].father != x) //路径压缩
{
y = nf[x].father;
nf[x].father = j; //将x作为根j的儿子
x = y; //向上一层
}
return a; //返回集合名
}

//将a和b合并成集合c
void _union(int a,int b,int c,ufNode nf[],int root[])
{
int i = root[a],j = root[b];
if(nf[i].count > nf[j].count)
{
int x;
x = i;
i = j;
j = x;
}
nf[i].father = j;
nf[j].count += nf[i].count;
nf[j].name = c;
root[c] = j;
}



堆排序:
 <1.堆的定义:堆是每个非叶结点值都大于或等于其儿子值(简称“父大于子”)的完全二叉树。于是,根结点存储的就是树中的最大值。这样定义的堆成为“大根堆”。 若根结点储存的是树中的最小值,那么这样的堆称为“小根堆”。
<2.排序阶段。
<3.重新堆化。

堆排序算法由两个函数组成,heapify是重新堆化函数,heap_sort是排序的主控函数。


void heapify(int a[],int i,int j) //i表示需要操作的根结点,j表示堆元素下标的上界
{
int k,x;
k = 2 * i; //i的左儿子
x = a[i];
while(k <= j)
{
if(k < j)
if(a[k] < a[k + 1]) k = k + 1; //比较左右儿子,取大的值
if(x >= a[k])break; //若根结点大于左右儿子,则跳出
else
{
a[i] = a[k];
i = k;
k = a * i;
}
}
a[i] = x;
}



void heap_sort(int a[],int n)
{
for(int i = n / 2;i >= 1;i --) heapify(a,i,n); //堆初始化
for(int i = n;i > 1;i --) //将根和最后一片叶交换
{
int x = a[1];
a[1] = a[i];
a[i] = x;
heapify(a,1,i - 1); //重新堆化
}
}


  评论这张
 
阅读(172)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018