最小生成樹演算法prim
1. 什麼是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;
}
2. Prim演算法 最小生成樹問題
你的圖里有兩條邊權重一樣，在實際計算前無法事先保證最小生成樹的唯一性，即使是兩個不同的Prim演算法也可能產生不同的結果
當然，計算完之後情況會略有不同，下面會解釋
Prim演算法首先會依次選
E(1,2)=1
E(2,7)=2
E(2,3)=3
然後E(3,4)=E(7,6)=4，會面臨兩種選擇
如果優先選E(3,4)這條邊，那麼下一步仍然會選E(7,6)，反過來也一樣，所以這個圖恰好沒影響
繼續下去最終得到
E(1,2)=1
E(2,7)=2
E(2,3)=3
E(3,4)=4
E(7,6)=4
E(4,5)=6
這樣6條邊構成唯一的最小生成樹，總權重是20
（唯一性是因為總權重不超過20的其它子圖確實都不連通）
既然最小生成樹唯一，Kruskal演算法當然也會產生同一棵樹
3. 話說最小生成樹的prim演算法和kursual演算法的區別
prim演算法和kurskal演算法解決的問題是相同的，都用來求最小生成樹。從某一結點A出發，按照一定次序，經過中間結點集Q中的每一個結點，得到最短路徑，稱為最小生成樹。
kurskal演算法的核心思想就是「盡可能的選取短邊」，按照長度從小到大依次加入生成樹；prim演算法引入一個概念——生長點（和非生長點），每次加入的最短邊是與生長點相鄰的最短邊，初始狀態下，唯一的一個點就是生長點，隨著新邊的加入，每次加入的邊的末端就是生長點，若某一生長點已經沒有相鄰邊可以加入，就回溯到上一級結點，加入新邊，直到Q中的所有結點都加入圖中。
一般教材編的都很清楚的，結合我這個，再看看書，相信你很快就會明白的。
4. 急！數據結構最小生成樹prim演算法C語言實現
Kruskal演算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化輔助數組
k=1; //k表示當前構造最小生成樹的第幾條邊,初值為1
j=0; //E中邊的下標,初值為0
while (k<n) //生成的邊數小於n時循環
{
m1=E[j].u;m2=E[j].v; //取一條邊的頭尾頂點
sn1=vset[m1];sn2=vset[m2]; //分別得到兩個頂點所屬的集合編號
if (sn1!=sn2) //兩頂點屬於不同的集合,該邊是最小生成樹的一條邊
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成邊數增1
for (i=0;i<n;i++) //兩個集合統一編號
if (vset[i]==sn2) //集合編號為sn2的改為sn1
vset[i]=sn1;
}
j++; //掃描下一條邊
}
}
Prim演算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //給lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1個頂點
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 邊(%d,%d)權為:%d/n",closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<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;
}
}
}
5. 什麼是最小生成樹的prim演算法
/*
鄰接矩陣存儲圖
測試數據
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/
#include <stdio.h>
#include <limits.h>
#define N 100
int p[N], key[N], tb[N][N];
void prim(int v, int n)
{
int i, j;
int min;
for (i = 1; i <= n; i++)
{
p[i] = v;
key[i] = tb[v][i];
}
key[v] = 0;
for (i = 2; i <= n; i++)
{
min = INT_MAX;
for (j = 1; j <= n; j++)
if (key[j] > 0 && key[j] < min)
{
v = j;
min = key[j];
}
printf("%d%d ", p[v], v);
key[v] = 0;
for (j = 1; j <= n; j++)
if (tb[v][j] < key[j])
p[j] = v, key[j] = tb[v][j];
}
}
int main()
{
int n, m;
int i, j;
int u, v, w;
while (scanf("%d%d", &n, &m))
{
for(i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
tb[i][j] = INT_MAX;
}
while (m--)
{
scanf("%d%d%d", &u, &v, &w);
tb[u][v] = tb[v][u] = w;
}
prim(1, n);
printf("\n");
}
return 0;
}
6. 用Prim演算法求最小生成樹
7. 利用Prim（普里姆）演算法 構造最小生成樹 程序
演算法同樣是解決最小生成樹的問題。
其演算法為：在這n個點中的相通的邊進行排序，然後不斷地將邊添加到集合中（體現了貪心的演算法特點），在並入集合之前，必須檢查一下這兩點是不是在一個集合當中，這就用到了並查集的知識。直到邊的集合達到了n-1個。
與prim演算法的不同：prim演算法為單源不斷尋找連接的最短邊，向外擴展，即單樹形成森林。而Kruskal演算法則是不斷尋找最短邊然後不斷將集合合並，即多樹形成森林。
復雜度的不同：prim演算法的復雜度是O(n^2),其中n為點的個數。Kruskal演算法的復雜度是O(e*loge)，其中e為邊的個數。兩者各有優劣，在不同的情況下選擇不同的演算法。
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=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
{先選定一個點，然後從該點出發，與該點相連的點取權值最小者歸入集合，然後再比較在集合中的兩點與其它各點的邊的權值最小者，再次進入集合，一直到將所有的點都歸入集合為止。}
8. 最小生成樹是什麼
1.生成樹從前述的深度優先和廣度優先遍歷演算法知，對於一個擁有n個頂點的無向連通圖，它的邊數一般都大於n－1。生成樹是指在連通圖中，由n個頂點和不構成迴路的n－1條邊構成的樹。若由深度優先遍歷得到的生成樹稱為深度優先生成樹，則由廣度優先遍歷得到的生成樹稱為廣度優先生成樹。再進一步分析可知，對於滿足條件，連通圖的n個頂點和不構成迴路的n－1條邊構成的生成樹有多棵，換言之，圖的生成樹不唯一。2.最小生成樹對於帶權的圖，其生成樹的邊也帶權，在這些帶權的生成樹中必有一棵邊的權值之和最小的生成樹，這棵生成樹就是最小（代價）生成樹。
最小生成樹在實際中具有重要用途，如在通信網的設計中，用頂點表示城市，用邊表示兩個城市之間的通信線路，邊的權值表示建造通信線路的費用，這n個城市之間最多可以建n（n－1）／2條線路。如果要求在任意兩個城市之間都有線路相連，且建設費用最少，即從n（n－1）／2條邊中選取權值最小的n－1條，這就是最小生成樹問題。2.構造最小生成樹的基本原則（1）盡可能選取權值最小的邊，但不能構成迴路。
（2）選擇n－1條邊構成最小生成樹。
常見的最小生成樹演算法有普里姆（Prim）演算法和克魯斯卡爾（kruskal）演算法兩種。
9. 最小生成樹 prim
"prim不是這樣描述的嗎？從一個點出發，列出這個點所有鄰接的邊，選擇最小的邊假如到樹中，然後從另一個端點開始，一樣操作就可以嘛？"--------應該是「從一個點出發，列出這個點所有鄰接的邊，選擇最小的邊，將所連頂點到樹中，再到剩餘的點中找與這兩點（其中之一）距離最小的點加入之中。」然後循環就行了