No.8.2 图的最小生成树-Prim算法

一、上节中的最小生成树，使用了快速排序算法；这节的最小生成树，模拟Dijkstra算法

　　1.既然是找一条路（最小生成树），将所有节点连接起来，那么随便选择一个顶点先，然后从这个顶点出发的边中，挑一个最短的边；然后再找一个距离这两个顶点最近的边和顶点，加入到图中，同时要避免回路；依次类推，直到加入图的顶点数 == 顶点数。

　　2.是不是有点像Dijkstra算法：先固定一个点，找到距离源点A最近的一个点B；然后固定点B，再找到距离B最近的点。。。

　　3.不同的地方就在于：Dijkstra算法是寻找的各顶点到源点的最短距离 dis[k] > dis[j] + e[j][k]；最小生成树，则是寻找所有树外顶点到任一个生成树顶点的最短距离 dis[k] > e[j][k]；

　　什么意思呢？

　　a. 比如现在树节点(1,2,4)，非树节点(3,5,6)，新加入的树节点是4（可以认为 dis[4]=0），扫描以4为初始点的边4->5，并比对 dis[5] 的值，(此时Dijkstra算法 dis[k] > dis[j] + e[j][k] = e[j][k] )，说明通过此时的树节点 4，可以使非树节点 5 到某个树节点的距离变短；

　　b. 更新 dis 数组，再找到非树节点中的最小值加入到树节点；

　　c. 继续以新加入的节点更新非树节点到树节点的距离！

二、CODE

# include

int main(){
　　int i,j,k, t1,t2,t3;
　　int min,n,m;
　　int inf= 999999;
　　int book[7]={0};
　　int e[7][7],dis[7];
　　int count=0,sum=0;

　　scanf("%d %d", &n,&m);
　　for(i=1;i<=n;i++)
　　　　for(j=1;j<=n;j++){
　　　　　　if(i==j) e[i][j]=0;
　　　　　　else e[i][j]=inf;
　　　　}

　　for(i=1;i<=m;i++){ 　　//无向图
　　　　scanf("%d %d %d",&t1,&t2,&t3);
　　　　e[t1][t2]=t3;
　　　　e[t2][t1]=t3;
　　}

　　for(i=1;i<=n;i++) 　　//先将 1 加入生成树，并更新非树节点到树节点(1,)的距离
　　　　dis[i]=e[1][i];
　　book[1]=1;
　　count++;

　　while(count 　　　　min=inf;
　　　　for(i=1;i<=n;i++){ 　　//在非树节点中，找出最短路径
　　　　　　if(book[i]==0 && dis[i] 　　　　　　　　min=dis[i];
　　　　　　　　j=i;
　　　　　　}
　　　　}
　　　　book[j]=1;
　　　　count++;
　　　　sum=sum+dis[j];

　　　　for(k=1;k<=n;k++){ 　　//扫描当前顶点 j 的所有边，并以 j 为中间点，更新生成树到非树节点的距离
　　　　　　if(book[k]==0 && dis[k] >e[j][k])
　　　　　　dis[k]=e[j][k];
　　　　}
　　}

　　printf("%d ",sum);
　　getchar();return 0;
}

显然，这种方法的时间复杂度是O(N*N)。

三、堆优化查询，邻接表优化存储

　　dis[ ] 记录生成树到树外顶点的距离；

　　h[ ]是一个最小堆，以边长为准，存储的是顶点编号；

　　pos[ ]记录每个顶点在最小堆中的位置；

int dis[7],book[7]={0};
int h[7],pos[7],size;

void swap(int x,int y){　　//交换两个点的位置，包括 h /.pos
　　int t;
　　t=h[x];
　　h[x]=h[y];
　　h[y]=t;

　　//h[x], h[y] 这两个变量仅仅是完成值的交换

　　t=pos[h[x]];　　// h[x] h[y] 在上面已经交换过，但是并不影响这里的pos交换
　　pos[h[x]]=pos[h[y]];
　　pos[h[y]] = t;
}

void siftdown(int i){　　//用于生成最小堆
　　int t,flag=0;
　　while(i*2<=size && flag==0){
　　　　if(dis[h[i]]>dis[h[i*2]])　　//先尝试左子树的比较
　　　　　　t=i*2;
　　　　else
　　　　　　t=i;
　　　　if(dis[h[t]] > dis[i*2+1])　　//在之前的比较结果基础上，再比较有子树（如果存在的话）
　　　　　　t=2*i+1;
　　　　if(t!=i){
　　　　　　swap(t,i);
　　　　　　i=t;
　　　　}
　　　　else
　　　　　　flag=1;
　　}
}

void siftup(int i){
　　int flag=0;
　　if(i==1) return;
　　while(i!=1 && flag==0){
　　　　if(dis[h[i]] 　　　　　　swap(i,i/2);
　　　　else
　　　　　　flag=1;
　　　　i=i/2;
　　}
}

int pop(){
　　int t;
　　t=h[1];
　　pos[t]=0;
　　h[1]=h[size];
　　pos[h[1]]=1;
　　size--;
　　siftdown(1);
　　return t;
}

int main(){
　　int n,m,i,j,k;
　　int u[19],v[19],w[19],first[7],next[19];　　//模拟邻接表
　　int inf=999999;
　　int count=0,sum=0;

　　scanf("%d %d",&n,&m);
　　for(i=1;i<=m;i++)
　　　　scanf("%d %d %d",&u[i],&v[i],&w[i]);

　　for(i=m+1;i<=2*m;i++){　　//无向图，每条边正反存储两次，这样就不存在 first[i] = -1 的情况
　　　　u[i]=v[i-m];
　　　　v[i]=u[i-m];
　　　　w[i]=w[i-m];
　　}

　　//邻接表

　　for(i=1;i<=n;i++) first[i]=-1;
　　for(i=1;i<=2*m;i++){
　　　　next[i] = first[u[i]];
　　　　first[u[i]]=i;
　　}

　　book[1]=1;　　//从源点 1 开始
　　count++;

　　dis[1]=0;
　　for(i=2;i<=n;i++) dis[i]=inf;
　　k=first[1];
　　while(k!=-1){　　//依据从点1出发的边，更新dis[ ]数组
　　　　dis[v[k]]=w[k];
　　　　k=next[k];
　　}

　　size=n;
　　for(i=1;i<=size;i++) {h[i]=i; pos[i]=i;}
　　for(i=size/2;i>=1;i--) {siftdown(i);} // i -> h[i] ，由siftdown根据边长生成最小堆h，swap对应h->pos
　　pop();　　//当前顶点肯定是1，先pop

　　while(count 　　　　j=pop();　　　  //取最小堆的顶端顶点（边长最小）
　　　　book[j]=1;
　　　　count++;
　　　　sum=sum+dis[j];

　　　　k=first[j];　　//以顶点 j 为中间节点，对非树节点进行松弛
　　　　while(k!=-1){
　　　　　　if(book[v[k]]==0 && dis[v[k]]>w[k]){
　　　　　　　　dis[v[k]]=w[k];

　　　　　　　　//如果距离有更新（变小），需要对顶点 v[k] 所在 h 中的位置重新调整（向上）

　　　　　　　　siftup(pos[v[k]]);　　
　　　　　　}
　　　　　　k=next[k];
　　　　}
　　}
　　printf("%d ",sum);
　　getchar();getchar();return 0;
}

三、小结

Kruskal算法是一步步地将森林中的树进行合并；而Prim算法则是通过每次增加一条边来建立一棵树。

Kruskal算法更适合稀疏图；Prim算法在未使用堆优化时适合稠密图，使用了堆优化后适合稀疏图！