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算法
17 关键部分程序清单) I 1 课程设计介绍 1.1 课程设计内容编写算法能够建立带权图,并能够用 Kruskal 算法求该图的 最小生成树。 最小生成树能够选择图上的...
最小生成树(Prim、Kruskal算法)整理版
最小生成树(Prim、Kruskal算法)整理版_计算机软件及应用_IT/计算机_专业资料。pascal,我整理的,希望能帮助大家,包括了原理+代码+优化代码 ...
求最小生成树(Kruskal算法)实验报告
(Kruskal 算法) □演示性实验 □验证性实验 W101 赵晓平 实验仪器台号 实验日期及节次 □选修 □综合性实验 实验地点 指导教师 2013.12.12(四) 89A 节 一、...
经典最小生成树prim与kruskal算法分析比较
经典最小生成树prim与kruskal算法分析比较_计算机软件及应用_IT/计算机_专业资料。经典最小生成树 prim 与 kruskal 算法分析比较 例题 农民约翰被选为他们镇的镇长!...
Kruskal算法求解过程 离散数学
Kruskal算法求解过程 离散数学_理学_高等教育_教育专区。Kruskal算法求解过程 离散数学 算法(避圈法) Kruskal 算法(避圈法)求解过程 一、算法用途:求解无向连通加权...
关于Kruskal算法的环路判定问题研究
关于Kruskal算法的环路判定问题研究_专业资料。龙源期刊网 http://www.qikan.com.cn 关于 Kruskal 算法的环路判定问题研究 作者:曹睿 来源:《现代电子技术》2013 年...
数学建模-最小生成树-kruskal算法及各种代码
算法及代码 kruskal 算法及代码 ---含伪代码、 代码、matlab、 ---含伪代码、c 代码、matlab、pascal 等代码 含伪代码 K r u s k a l 算法每次选择 n-...
Kruskal算法伪代码
K​r​u​s​k​a​l​算​法​伪​代​码 暂无评价|0人阅读|0次下载|举报文档1. 初始化:U=V; TE={ }; 2. 循环直到 T 中的...
最小生成树Kruskal算法报告
("***欢迎进入最小生成树 Kruskal 算法***\n\n"); do { switch(menu()) { case 1:creat(&ga);break; case 2:find(&ga);break; case 3:choice...
最小生成树的Kruskal算法实验报告
大连民族学院 计算机科学与工程学院实验报告 实验题目: 最小生成树的 Kruskal 算法 课程名称: 离散数学 实验类型:□演示性 □验证性 □操作性 ■设计性 □综合性...
更多相关标签:
kruskal    熊猫算法    百度石榴算法    prim算法    最小生成树    贪心算法    迪杰斯特拉算法    a*算法    

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

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