9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

Kruskal算法



Kruskal 算法 算法思想
K r u s k a l 算法每次选择 n- 1 条边,所使用的贪婪准则是:从剩下的边中选择一条不 会产生环路的具有最小耗费的边加入已选择的边的集合中。 注意到所选取的边若产生环路则 不可能形成一棵生成树。K r u s k a l 算法分 e 步,其中 e 是网络中边的数目。按耗费 递增的顺序来考虑这 e 条边,每次考虑一条边。当考虑

某条边时,若将其加入到已选边的 集合中会出现环路,则将其抛弃,否则,将它选入。 初始时没有任何边被选择。边( 1 , 6)是最先选入的边,它被加入到欲构建的生成树中, 得到图 1 3 - 1 2 c。下一步选择边( 3,4)并将其加入树中(如图 1 3 - 1 2 d 所示)。 然后考虑边( 2,7 ,将它加入树中并不会产生环路,于是便得到图 1 3 - 1 2 e。下一步 考虑边( 2,3)并将其加入树中(如图 1 3 - 1 2 f 所示)。在其余还未考虑的边中,(7, 4)具有最小耗费,因此先考虑它,将它加入正在创建的树中会产生环路,所以将其丢弃。 此后将边( 5,4)加入树中,得到的树如图 13-12g 所示。下一步考虑边( 7,5),由于 会产生环路,将其丢弃。最后考虑边( 6,5)并将其加入树中,产生了一棵生成树,其耗 费为 9 9。图 1 - 1 3 给出了 K r u s k a l 算法的伪代码。 (2)pascal 代码 { 最小生成树的 Kruskal 算法。 Kruskal 算法基本思想: 每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点,将边加入 MST,并将所在 的 2 个连通分量合并,直到只剩一个连通分量 排序使用 Quicksort(O(eloge)) 检查是否在同一连通分量用 Union-Find,每次 Find 和 union 运算近似常数 Union-Find 使用 rank 启发式合并和路径压缩 总复杂度 O(eloge)=O(elogv) (因为 e<n(n-1)/2) } const maxn=100; maxe=maxn*maxn;

type edge=record a,b len end; var edges :array[0..maxe]of edge; p,r :array[0..maxn]of integer; 的 rank 启发式 n,e :integer; //保存所有边的信息 //p[i]保存 i 的父亲节点, 用来实现 Union-Find r :integer; :integer; //边的 2 个顶点 //边的长度

//n 为顶点数,e 为边数 //交换

procedure swap(a,b:integer); begin edges[0]:=edges[a]; edges[a]:=edges; edges:=edges[0]; end;

procedure quicksort(l,r:integer); var x,i,j :integer; begin x:=edges[random(r-l+1)+l].len; i:=l;j:=r; repeat

//快速排序

while edges[i].len<x do inc(i); while edges[j].len>x do dec(j); if i<=j then begin swap(i,j); inc(i);dec(j); end until i>j; if l<j then quicksort(l,j); if i<r then quicksort(i,r); end; procedure init; var i begin assign(input,'g.in');reset(input); readln(n,e); for i:=1 to e do readln(edges[i].a,edges[i].b,edges[i].len); 信息 for i:=1 to n do p[i]:=i; randomize; quicksort(1,e); end; function find(x:integer):integer; //并查集的 Find,用来判断 2 个顶点是否属于 //使用快速排序将边按权值从小到大排列 //初始化并查集 //从文件读入图的 :integer;

一个连通分量 begin if x<>p[x] then p[x]:=find(p[x]); find:=p[x] end; procedure union(a,b:integer); 连通分量 var t begin a:=find(a);b:=find(b); if r[a]>r then begin t:=a;a:=b;b:=t end; if r[a]=r then inc(r); p[a]:=b; end; procedure kruskal; var en :integer; //en 为当前边的编号 //统计进行了几次合并。n-1 次合并后就得到最小生成树 //统计最小生成树的边权总和 //主过程 :integer; //如果不属于且权值最小则将 2 个顶点合并到一个

count :integer; tot begin :integer;

count:=0;en:=0; tot:=0; while count<n-1 do

begin inc(en); with edges[en] do begin if find(a)<>find(b) then begin union(a,b); writeln(a,'--',b,':',len); inc(tot,len); inc(count); end; end; end; writeln('Total Length=',tot) end; {===========main==========} begin init; kruskal; end.



更多相关文章:
数据结构课程设计报告最小生成树Kruskal算法
合肥学院 计算机科学与技术系 课程设计报告 2014-2015 学年第二学期 课学学专指业导班教生姓 程名号级师 数据结构 Kruskal 算法求最小生成树 姚国栋 1204091021...
最小生成树(Prim、Kruskal算法)整理版
最小生成树(Prim、Kruskal算法)整理版_计算机软件及应用_IT/计算机_专业资料。pascal,我整理的,希望能帮助大家,包括了原理+代码+优化代码 ...
经典最小生成树prim与kruskal算法分析比较
经典最小生成树prim与kruskal算法分析比较_计算机软件及应用_IT/计算机_专业资料。经典最小生成树 prim 与 kruskal 算法分析比较 例题 农民约翰被选为他们镇的镇长!...
Kruskal算法说明及图解
Kruskal算法说明及图解_计算机软件及应用_IT/计算机_专业资料。数据结构kruskal最小生成树算法1.无向网图及边集数组存储示意图 V1 V0 V5 V4 V2 V3 vertex[6]...
Kruskal算法求解过程 离散数学
Kruskal算法求解过程 离散数学_理学_高等教育_教育专区。Kruskal算法求解过程 离散数学 算法(避圈法) Kruskal 算法(避圈法)求解过程 一、算法用途:求解无向连通加权...
最小生成树的Kruskal算法实验报告
大连民族学院 计算机科学与工程学院实验报告 实验题目: 最小生成树的 Kruskal 算法 课程名称: 离散数学 实验类型:□演示性 □验证性 □操作性 ■设计性 □综合性...
Kruskal算法求最小生成树.doc
2.Kruskal 算法在扫描到邻接矩阵存放的信息后,用冒泡排序将边上的权值从小到 大排列。定义一个辅助数组,该数组是用来判断生成树中是否会出现回路,也就是生成 正确...
用prim算法和Kruskal算法求最小生成树
用prim算法和Kruskal算法求最小生成树_计算机软件及应用_IT/计算机_专业资料。用 prim 算法和 Kruskal 算法求最小生成树 2013-10-15 星期二 一、 问题表述分别用...
分别利用prim算法和kruskal算法实现求图的最小生成树
分别利用prim算法和kruskal算法实现求图的最小生成树_工学_高等教育_教育专区。数据结构 /*分别利用 prim 算法和 kruskal 算法实现求图的最小生成树*/ #include<...
最小生成树kruskal算法
最小生成树kruskal算法_工学_高等教育_教育专区。哈工大软设,c++实现最小生成树kruskal算法 /*最小生成树 kruskal 算法*/ #include<iostream> #define maxn 20 ...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图