Prim算法的简单分析

Prim算法主要的思路：将点集一分为二，通过找到两个点集之间的最短距离，来确定最小生成树，每次确定最短距离后，对两个点集进行更新。

具体的实现过程：难点就是如何找到两个点集之间的最短距离，这里设置两个数组，lowcost[i],mst[i],分别表示以i为终点的边和对应的起点，有了这两个数组就能够顺利的进行状态更新了。（整个代码与dijstra算法惊人的相似），大家可以将两者对比起来看。

代码：

#include <iostream>
#define  INF 99999999
#include <string.h>
using namespace std;

int a[110][110];
int lowcost[110];//lowcost[i]表示以i为终点的最短距离，
int mst[110];//mst[i]对应的lowcost[i]的起点

//默认的起点为1
void prim(int n){
    int minl,tmp;
    int flag[110];
    for(int i=1;i<=n;i++)
      mst[i]=1;
    for(int i=1;i<=n;i++)
      lowcost[i]=a[1][i];
    memset(flag,0,sizeof(flag));
    for(int k=2;k<=n;k++){
        minl=INF;
    for(int i=2;i<=n;i++){
       if(flag[i]==0&&lowcost[i]<minl){
         minl=lowcost[i];
         tmp=i;
       }
    }
    cout<<'V'<<mst[tmp]<<" "<<'V'<<tmp<<" "<<minl<<endl;
   for(int i=2;i<=n;i++){
      if(a[tmp][i]<lowcost[i]&&a[tmp][i]>0){
       lowcost[i]=a[tmp][i];
       mst[i]=tmp;
      }
    }
    flag[tmp]=1;
    }
}

int main(){
    int n,m;
    int x,y,path;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
       for(int j=1;j<=n;j++){
         if(i==j)
         a[i][j]=0;
         else
         a[i][j]=INF;
       }
    }
    for(int i=1;i<=m;i++){
      cin>>x>>y>>path;
      a[x][y]=a[y][x]=path;
    }
    prim(n);
    return 0;
}