当前位置:首页 >> 学科竞赛 >>

最小生成树


Kruskal算法 - pascal语言
program didi;
var a:array[0..100000] of record
s,t,len:longint;
end;
fa,r:array[0..10000] of longint;
n,i,j,x,y,z:longint;
tot,ans:longint;
count,xx:longint;
procedure quick(l,r:longint);
var i,j,x,y,t:longint;
begin
i:=l; j:=r;
x:=a[(l+r) div 2].len;
repeat
while x>a[i].len do inc(i);
while x<a[j].len do dec(j);
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then quick(i,r);
if l<j then quick(l,j);
end;
function find(x:longint):longint;
begin
if fa[x]=x then exit(x);
fa[x]:=find(fa[x]);{路径压缩}
exit(fa[x]);
end;
procedure union(x,y:longint);{启发式合并}
var
t:longint;
begin
x:=find(x);
y:=find(y);
if r[x]>r[y] then
begin
t:=x; x:=y; y:=t;
end;
if r[x]=r[y] then inc(r[x]);
fa[x]:=y;
end;
begin
readln(xx,n);
for i:=1 to xx do fa[i]:=i;
for i:=1 to n do
begin
read(x,y,z);
inc(tot);
a[tot].s:=x;
a[tot].t:=y;
a[tot].len:=z;
end;
quick(1,tot);{将边排序}
ans:=0;
count:=0;
i:=0;
while count<=x-1 do{count记录加边的总数}
begin
inc(i);
with a[i] do
if find(s)<>find(t) then
begin
union(s,t);
ans:=ans+len;
inc(count);
end;
end;
write(ans);
end.
Prim算法 - pascal语言
var m,n:set of 1..100;
s,t,min,x,y,i,j,k,l,sum,p,ii:longint;
a:array[1..100,1..100]of longint;
begin
readln(p);
for ii:=1 to p do
begin
k:=0; sum:=0;
fillchar(a,sizeof(a),255);
readln(x);
m:=[1];
n:=[2..x];
for i:=1 to x do
begin
for j:=1 to x do
begin
read(a[i,j]);
if a[i,j]=0
then a[i,j]:=maxlongint;
end;
readln;
end;
for l:=1 to x-1 do
begin
min:=maxlongint;
for i:=1 to x do
if i in m
then begin
for j:=1 to x do
begin
if (a[i,j]<min)and(j in n)
then begin
min:=a[i,j];
s:=i;
t:=j;
end;
end;
end;
sum:=sum+min;
m:=m+[t];
n:=n-[t];
inc(k);
end;
writeln(sum);
end;
end.

相关文章:
最小生成树问题
最小生成树问题_工学_高等教育_教育专区。5.6 题 最小生成树问题 实习报告 题目:最小生成树问题 班级: 姓名: 学号: 完成日期:2015.1.7 一.需求分析【问题...
最小生成树Kruskal算法报告
("2:找出最小生成树及所对应边\n"); printf("3:选择根结点编号\n"); printf("4:退出\n"); printf("请输入 1-4 选项\n"); 17 沈阳航空航天大学...
实验八 图的最小生成树
2、 编写生成最小生成树的 Prim 算法函数 void Prim(adjmatrix G, edgset CT, int n) 以及输出边集数组的函数 void PrintEdge(edgeset CT, int n)。 3...
,图的遍历及最小生成树实验报告
2. 利用普里姆算法求网络的最小生成树。 3. 实现构造生成树过程中的连通分量抽象数据类型。 4. 以文本形式输出对应图的最小生成树各条边及权值。 三、实验要求...
最小生成树and最短路径
最小生成树 and 最短路径无独有偶,在两个学期的期末中两门不同的科目《离散数学》和《数据结构》中都谈到 了图及其衍生的最小生成树、最短路径问题,并给出...
数据结构,最小生成树克鲁斯卡尔算法的实现
数据结构,最小生成树克鲁斯卡尔算法的实现_其它课程_高中教育_教育专区。数据结构课程设计 摘 要 设计了一个用 C/C++编写程序实现克鲁斯卡尔最小生成树算 法,该...
最小生成树算法实验报告
最小生成树算法实验报告_计算机软件及应用_IT/计算机_专业资料。作业 1 最小生成树的生成算法 1.1 算法应用背景在实际生活中, 图的最小花费生成树问题有着广泛...
最小生成树求解-数据结构与算法课程设计报告
用 -1- 数据结构与算法课程设计报告 2 问题分析和任务定义本课程设计重在使用 prim 算法实现任意给定的网和起点的图的所有最小生成树的求 解,实现本课程设计的...
最小生成树论文
最小生成树 最小生成树问题摘要:本文通过对最小生成树两种算法(Kruskal 算法和 Prim 算法)的分析,用 C 语言写出了 Kruskal 算法的 C 语言源程序,通过计算机实现...
最小生成树问题
专业课程设计任务书学生姓名 题目 课题性质 指导教师 工程设计 最小生成树问题 课题来源 同组姓名 自拟命题 在 n 个城市之间架设通信网络, 只需保证连通即可, 求...
更多相关标签: