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

最小生成树


Kruskal算法 - pascal语言
program didi;
var a:array[0..100000] of record
s,t,len:longint;
end;
fa,r:arra

y[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.

相关文章:
图的存储方法与最小生成树
图的存储方法与最小生成树_计算机软件及应用_IT/计算机_专业资料。数据结构与算法实验名称: 班类级: 型: 10 软工转本 1 班 综合 姓名: 季佳宾 鹤琴 404 ...
实验八 图的最小生成树
2、 编写生成最小生成树的 Prim 算法函数 void Prim(adjmatrix G, edgset CT, int n) 以及输出边集数组的函数 void PrintEdge(edgeset CT, int n)。 3...
构造可以使n个城市连接的最小生成树
c. 从 E 中删除此最小边,转 b 继续执行,直到 k=n-1, 算法结束 d. 判断是否构成回路的方法: 设置集合 S,其中存放已加入到生成树中的边所连接的顶点集合...
最小生成树(Prim、Kruskal算法)整理版
最小生成树(Prim、Kruskal算法)整理版_计算机软件及应用_IT/计算机_专业资料。pascal,我整理的,希望能帮助大家,包括了原理+代码+优化代码 ...
数据结构课程设计-最小生成树
最小生成树 [摘要]选择一颗生成树,使之总的消费最少,也就是要构造连通网 的最小代价生成树(简称为最小生成树)的问题,一颗生成树的代价 就是树上各边的代价...
构造可以使N个城市连接的最小生成树
构造可以使 N 个城市连接的最小生成树 专业: ___ 班级: ___ 姓名: ___ 学号: ___ 完成日期: ___ 【问题描述】给定一个地区的 n 个城市间的距离网...
最小生成树
3.克鲁斯卡尔算法的思想为 假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔 算法构造最小生成树的过程为: (1)先构造一个只含 n 个顶点...
,图的遍历及最小生成树实验报告
2. 利用普里姆算法求网络的最小生成树。 3. 实现构造生成树过程中的连通分量抽象数据类型。 4. 以文本形式输出对应图的最小生成树各条边及权值。 三、实验要求...
两种算法实现最小生成树
得到的就是此图的最小生成树。 1 第二章 概要设计 2.1 抽象数据类型 ADT Graph { 数据对象 V:V 是具有相同特性的数据元素的和,称为顶点级。 数据关系 R...
最小生成树和最短路径 数据结构实验
最小生成树和最短路径 数据结构实验_计算机软件及应用_IT/计算机_专业资料。June 18 实验报告姓名:陈斌 2015 数据结构 第八次实验 学号:E11314079 专业:13 ...
更多相关标签:
最小生成树算法 | 最小生成树prim算法 | 生成树 | 什么是最小生成树 | 最小生成树的应用 | prim | 最大生成树 | kruskal算法 |