kruskal算法：(贪心).txt

Kruskal算法：(贪心)

按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点v所在的集合}
 var i:integer;
 begin
   i:=1;
   while (i<=n) and (not v in vset[i]) do inc(i);
   if i<=n then find:=i else find:=0;
 end;

procedure kruskal;
 var
   tot,i,j:integer;
 begin
   for i:=1 to n do vset[i]:=[i];{初始化定义n个集合，第I个集合包含一个元素I}
p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针}
sort;
{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}
   while p>0 do begin
     i:=find(e[q].v1);j:=find(e[q].v2);
     if i<>j then begin
       inc(tot,e[q].len);
       vset[i]:=vset[i]+vset[j];vset[j]:=[];
       dec(p);
     end;
     inc(q);
   end;
   writeln(tot);
 end;