Prim和Kruskal求最小生成树

Prim：

算法步骤：

1.任意结点开始（不妨设为v1）构造最小生成树： 2.首先把这个结点（出发点）包括进生成树里， 3.然后在那些其一个端点已在生成树里、另一端点还未在生成树里的所有边中找出权最小的一条边， 4.并把这条边、包括不在生成树的另一端点包括进生成树， …。 5.依次类推，直至将所有结点都包括进生成树为止

Pascal的渣渣代码...

注：寻找最短的边那一步可以用堆优化，但那样还不如直接用Kruskal......

Reference:　　http://www.nocow.cn/index.php/Prim%E7%AE%97%E6%B3%95

const vmax=1000;
var 
w:array[1..vmax,1..vmax] of longint;
i,j,k,v,e:longint;
w:存储邻接矩阵
v:结点数
e:边数

procedure prim(v0:longint);
var flag:array[1..vmax] of boolean;  //flag:表示是否在树中。true是, false否
      min,prevk,nextk:longint;
begin
 fillchar(flag,sizeof(flag),0);
 flag[v0]:=true;           //STEP2
 for i:=1 to v-1 do          //最小生成树中有v-1条边 ，所以外层循环需要v-1次        //STEP5
   begin
    min:=maxlongint;

    for k:=1 to v do  
      if flag[k] then  
        //寻找在最小生成树中的点  k：当前在最小生成树中的点
        for j:=1 to v do          //STEP3
          //寻找与（最小生成树中的点）的距离最短的点。
          // j：当前要找的不在最小生成树中的点 
          if (not flag[j]) and (w[k,j]<min) and (w[k,j]<>0) then
            紫色代码：//判重：要找的点不能在最小生成树中
            红色代码：//k与j必须相连！
            begin
            min:=w[k,j];
            nextk:=j;    
            prevk:=k;    
            //这条边从在最小生成树中的点出发 ，
            //扩展到当前不在最小生成树中的点。
            //prevk:=k，prevk为起点，在最小生成树中
            //nextk:=j，nextk为 终点，当前不在最小生成树中
            end;

    if min<>maxlongint then        
      //如果找到了nextk这样的可以从当前最小生成树中扩展出来
      //（可以进入最小生成树）的点
      begin
      flag[nextk]:=true;        //将nextk这样的点加入最小生成树    //STEP4
      writeln(prevk,‘ ’,nextk,‘ ’,min);           //输出这条边
      end;
   end;
end;


begin
fillchar(w,sizeof(w),0);
readln(v,e);
for k:=1 to e do
 begin
 read(i,j);
 readln(w[i,j]);
 w[j,i]:=w[i,j];
 end;

prim(1);       //STEP1

end.

View Code

Kruskal：

算法步骤：

1、把图中的边按权值从小到大排序。 2、按从小到大的顺序依次向树中加边。在添加每一条边（u，v）时，如果u和V两个点都已在树中，一旦添加，就回构成回路，所以放弃该边，在向后找下一条边。 3、直到添加n-1条边。

用并查集优化

#include <iostream>
using namespace std;

struct abc
{
    int x,y,dat;
};

struct abc e[1000];
int f[1000];
int i,j,k,ans,n,m,tx,ty,tmp;

int find(int x)
{
    if (x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}

void iunion(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if (fx!=fy)
        f[fy]=fx;
}

void qsort(int l,int r)
{
   int i,j,mid;
   struct abc t; 
   i=l;
   j=r;
   mid=e[(l+r)/2].dat;
   do{
       while (e[i].dat<mid) i++;
       while (e[j].dat>mid) j--;
       if (!(i>j))
       {
           t=e[i];
           e[i]=e[j];
           e[j]=t;
           i++;
           j--;
       }
   }while (i<=j);
   if (l<j) qsort(l,j);
   if (i<r) qsort(i,r);
}

int main()
{
    
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>tx>>ty>>tmp;
        e[i].x=tx;
        e[i].y=ty;
        e[i].dat=tmp;
    }

    for (i=1;i<=n;i++)
        f[i]=i;
    qsort(1,m);
    
    k=1;
    ans=0;
    for (i=1;i<=n-1;i++)
    {
        while (find(e[k].x)==find(e[k].y)) k++;
        iunion(e[k].x,e[k].y);
        ans=ans+e[k].dat;
        cout<<e[k].x<<" "<<e[k].y<<" "<<e[k].dat<<endl;
    }
    
    cout<<ans<<endl;
}

View Code