最小生成树算法.docx

文档介绍：最小生成树算法
一、概念篇
1、 树的概念
树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任 意两点间有且仅有一条路径，即图中不存在环，这样的图称为树。
2、 生成树的概念
对于一个无向连通图G=(V且图为完全图，所以如果采用朴素的穷举边的算法必然会超时， 因此我们采用小根堆进行优化。
程序代码：
const maxn=1000;
type sidetype=record
poi1,poi2,length:longint;
end;
var heap:array[0..maxn*maxn] of sidetype;｛堆｝
g:array[0..maxn,0..maxn] of longint;｛邻 接矩阵｝
hash:array[0..maxn] of boolean; ｛集合 V｝
n,i,j,k,top,ans:longint;
temp:sidetype;
procedure exchange(a,b:longint);
var tmp:sidetype;
begin
tmp:=heap[a];
heap[a]:=heap[b];
heap[b]:=tmp;
end;
procedure put(m:longint) ; ｛堆插入操作｝
begin
if m=1 then exit;
if heap[m].length<heap[m div 2].length then
begin
exchange(m,m div 2);
put(m div 2);
end;
end;
procedure push(m:longint);
begin
if m*2>top then exit;
if m*2=top then
begin
if heap[m].length>heap[m*2].length then exchange(m,m*2);
exit;
end;
if heap[m*2].length<heap[m*2+1].length then
begin
if heap[m].length>heap[m*2].length then
begin
exchange(m,m*2);
push(m*2);
end;
end else
begin
if heap[m].length>heap[m*2+1].length then
begin
exchange(m,m*2+1);
push(m*2+1);
end;
end;
end;
procedure dele(m:longint) ; ｛堆删除操作｝
begin
heap[1]:=heap[top];
dec(top);
push(1);
end;
begin
assign(input,'');
reset(input);
assign(output,'');
rewrite(output);
fillchar(g,sizeof(g),0);
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
read(g[i,j]);
readln;
end;
close(input);
fillchar(hash,sizeof(hash),false);
hash[1]:=true;
top:=0;
for i:=2 to n do
begin
inc(top);
heap[top].poi1:=1;
heap[top].poi2:=i;
heap[top].length:=g[1,i];
put(top);
end;
ans:=0;
for k:=1 to n-1 do
begin
while hash[heap[1].poi1] and hash[heap[1].poi2] do dele(1);如果堆根的边不满 足条件则删除｝
ans:=ans+heap[1].length;
temp:=heap[1];
dele(1);
if hash[]=false then
begin
hash[]:=true;
for i:=1 to n do
if hash[i]=false then
begin
inc(top);
heap[top].poi1:=;
heap[top].poi2:=i;
heap[top].length:=g[,i];
put(top);
end;
end else
begin