prim求最小生成樹演算法
① 什麼是Prim演算法
Prim演算法
Prim演算法用於求無向圖的最小生成樹
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
Prim演算法實現：
（1）集合：設置一個數組set[i](i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
參考程序
/* Prim.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */
#include "stdio.h"
#define maxver 10
#define maxright 100
int main()
{
int G[maxver][maxver],in[maxver]=,path[maxver][2];
int i,j,k,min=maxright;
int v1,v2,num,temp,status=0,start=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for(j=0;j<num;j++)
for(k=0;k<num;k++)
{
if(j==k)
G[j][k]=maxright;
else
if(j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if(temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if(temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
}
}
for(j=0;j<num;j++)
{
status=0;
for(k=0;k<num;k++)
if(G[j][k]<maxright)
{
status=1;
break;
}
if(status==0)
break;
}
do
{
printf("Please enter the vertex where Prim algorithm starts:");
scanf("%d",&start);
}while(start<0||start>num);
in[start-1]=1;
for(i=0;i<num-1&&status;i++)
{
for(j=0;j<num;j++)
for(k=0;k<num;k++)
if(G[j][k]<min&&in[j]&&(!in[k]))
{
v1=j;
v2=k;
min=G[j][k];
}
if(!in[v2])
{
path[i][0]=v1;
path[i][1]=v2;
in[v1]=1;
in[v2]=1;
min=maxright;
}
}
if(!status)
printf("We cannot deal with it because the graph is not connected!\n");
else
{
for(i=0;i<num-1;i++)
printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);
}
return 1;
}
Prim演算法。
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
參考程序
//Prim 演算法 讀入頂點數(n)、邊數(m)，邊的起始點和權值 用鄰接矩陣儲存
//例如
//7 12 (7個頂點12條邊)
//1 2 2
//1 4 1
//1 3 4
//2 4 3
//2 5 10
//3 4 2
//4 5 7
//3 6 5
//4 6 8
//4 7 4
//5 7 6
//6 7 1
#include <stdio.h>
#include <string.h>
int main()
{
int m , n;
int a[201][201] , mark[201] , pre[201] , dist[201];
int s , t , w;
int i , j , k , min , tot;
freopen("Prim.txt" , "r" , stdin);
//讀入數據
memset(a , 0 , sizeof(a));
scanf("%d %d" , &n , &m);
for (i = 0; i < m; i ++)
{
scanf("%d %d %d" , &s , &t , &w);
a[s][t] = w; a[t][s] = w;
}
//賦初值
memset(mark , 0 , sizeof(mark));
memset(pre , 0 , sizeof(pre));
memset(dist , 9999 , sizeof(dist));
dist[1] = 0;
//Prim
for (i = 1; i <= n; i ++)
{
min = 9999; k = 0;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (dist[j] < min)) {min = dist[j]; k = j;}
if (k == 0) break;
mark[k] = 1;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (a[k][j] < dist[j]) && (a[k][j] > 0))
{
dist[j] = a[k][j];
pre[j] = k;
}
}
tot = 0;
for (i = 1; i <= n; i ++) tot += dist[i];
printf("%d\n" , tot);
return 0;
}
② 圖所示是一個無向帶權圖,請分別按Prim演算法和Kruskal演算法求最小生成樹.
•普里姆（Prim）演算法
基本思想
假設N=(V,E)是一個具有n個頂點的連通網，T=(U,TE)是所求的最小生成樹，其中U是T的頂點集，TE是T的邊集。
（1）初始U={u0}(u0∈V),TE=φ；
（2）在所有u∈U,v∈V-U的邊中選一條代價最小的邊（u0，v0）並入集合TE，同時將v0並入U；
（3）重復（2），直到U=V為止。
此時，TE中必含有n-1條邊，則T=（V，{TE}）為N的最小生成樹。
注意：1.最小生成樹不唯一。
2.該圖從節點最小開始。