prim演算法的例題

⑴ 普里姆演算法的普里姆演算法的實現

為了便於在兩個頂點集U和V-U之間選擇權最小的邊，建立了兩個輔助數組closest和lowcost，它們記錄從U到V-U具有最小權值的邊，對於某個j∈V-U，closest[j]存儲該邊依附的在U中的頂點編號，lowcost[j]存儲該邊的權值。
為了方便，假設圖G採用鄰接矩陣g存儲，對應的Prim(g,v)演算法如下：
void Prim(MatGraph g,int v) //輸出求得的最小生樹的所有邊
{ int lowcost[MAXVEX]; //建立數組lowcost
int closest[MAXVEX]; //建立數組closest
int min,i,j,k;
for (i=0;i<g.n;i++) //給lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //構造n-1條邊
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k為最近頂點的編號
}
printf( 邊(%d,%d),權值為%d ,closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<g.n;j++) //修正數組lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
普里姆演算法中有兩重for循環，所以時間復雜度為O(n2)，其中n為圖的頂點個數。由於與e無關，所以普里姆演算法特別適合於稠密圖求最小生成樹。

⑵ 什麼是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演算法：是圖的最小生成樹的一種構造演算法。

假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在演算法執行結束時，TV=V，而 TE 是 E 的一個子集。在演算法開始執行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆演算法構造最小生成樹的過程為：在所有「其一個頂點已經落在生成樹上，而另一個頂點尚未落在生成樹上」的邊中取一條權值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。

如果看不懂還可以找一本數據結構的書看，這個演算法挺簡單的。

btw：其實你有空問，應該有空網路啊~網路就有了。懶得寫，我還是直接從網路過來的~

⑷ 這是一道數據結構問題，問題如下：對於如下圖所示的帶權無向圖，給出利用普利姆（Prim)演算法和克魯斯卡爾

自己按下面的先後過程畫圖即是生成過程；說雀雀明（i,j）是一條連接頂點i和j的一條邊；
普利姆（Prim)演算法：從頂點0開始頃世早構造
（0,1），（0,2），（1,2），（2,5），（5,4）
克魯斯卡爾演算法：
（0,1），（0,2），（返或1,2），（4,5），（2,5）