數(shù)據(jù)結(jié)構(gòu)算法:最小生成樹的算法實現(xiàn)

學(xué)數(shù)據(jù)結(jié)構(gòu)免不了要遇到最小生成樹的問題，下面我們就介紹最小生成樹的算法實現(xiàn)。
    A.Prim算法：
    procedure prim(v0:integer);
    var
    lowcost,closest:array[1..maxn] of integer;
    i,j,k,min:integer;
    begin
    for i:=1 to n do begin
    lowcost[i]:=cost[v0,i];
    closest[i]:=v0;
    end;
    for i:=1 to n-1 do begin
    {尋找離生成樹最近的未加入頂點k}
    min:=maxlongint;
    for j:=1 to n do
    if (lowcost[j]0) then begin
    min:=lowcost[j];
    k:=j;
    end;
    lowcost[k]:=0; {將頂點k加入生成樹}
    {生成樹中增加一條新的邊k到closest[k]}
    {修正各點的lowcost和closest值}
    for j:=1 to n do
    ifcost[k,j]    lowcost[j]:=cost[k,j];
    closest[j]:=k;
    end;
    end;
    end;{prim}
    B.Kruskal算法：(貪心)
    按權(quán)值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹。
    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為尚待加入的邊數(shù)，q為邊集指針}
    sort;
    {對所有邊按權(quán)值遞增排序，存于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;