普里姆演算法

1. 普里姆演算法的相關概念

1）生成樹一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。生成樹是對連通圖而言的，是連通圖的極小連通子圖，包含圖中的所有頂點，有且僅有n-1條邊。非連通圖的生成樹則組成一個生成森林；若圖中有n個頂點，m個連通分量，則生成森林中有n-m條邊。
2）和樹的遍歷相似，若從圖中某頂點出發訪遍圖中每個頂點，且每個頂點僅訪問一次，此過程稱為圖的遍歷，(Traversing Graph)。圖的遍歷演算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等演算法的基礎。圖的遍歷順序有兩種：深度優先搜索（DFS）和廣度優先搜索（BFS）。對每種搜索順序，訪問各頂點的順序也不是唯一的。
3）在一個無向連通圖G中，其所有頂點和遍歷該圖經過的所有邊所構成的子圖G′稱做圖G的生成樹。一個圖可以有多個生成樹，從不同的頂點出發，採用不同的遍歷順序，遍歷時所經過的邊也就不同。
在圖論中，常常將樹定義為一個無迴路連通圖。對於一個帶權的無向連通圖，其每個生成樹所有邊上的權值之和可能不同，我們把所有邊上權值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實際應用。例如，通訊線路鋪設造價最優問題就是一個最小生成樹問題。常見的求最小生成樹的方法有兩種：克魯斯卡爾(Kruskal)演算法和普里姆（Prim）演算法。

2. 什麼事普里姆演算法

是圖的最小生成樹的一種構造演算法。 假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在演算法執行結束時，TV=V，而 TE 是 E 的一個子集。在演算法開始執行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆演算法構造最小生成樹的過程為：在所有「其一個頂點已經落在生成樹上，而另一個頂點尚未落在生成樹上」的邊中取一條權值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。 補充：closedge的類型： struct { VertexData Adjvex; int Lowcost; }closedge[MAX_VERTEX_NUM]; //求最小生成樹的輔助數組 void MiniSpanTree_P( MGraph G, VertexType u ) { //用普里姆演算法從頂點u出發構造網G的最小生成樹 k = LocateVex ( G, u ); closedge[k].Lowcost = 0; // 初始，U＝{u} for ( j=0; j<G.vexnum; ++j ) // 輔助數組初始化 if (j!=k) closedge[j] = { u, G.arcs[k][j] }; for ( i=0; i<G.vexnum; ++i ) { 繼續向生成樹上添加頂點； } k = minimum(closedge); // 求出加入生成樹的下一個頂點(k) printf(closedge[k].Adjvex, G.vexs[k]); // 輸出生成樹上一條邊 closedge[k].Lowcost = 0; // 第k頂點並入U集 for (j=0; j<G.vexnum; ++j) //修改其它頂點的最小邊 if ( G.arcs[k][j] < closedge[j].Lowcost ) closedge[j] = { G.vexs[k], G.arcs[k][j] }; }

3. 什麼是普里姆演算法

構造最小生成樹用的，使用貪心策 略。prime演算法的基本思想 1.清空生成樹，任取一個頂點加入 生成樹 2.在那些一個端點在生成樹里，另 一個端點不在生成樹里的邊中，選 取一條權最小的邊，將它和另一個 端點加進生成樹 3.重復步驟2，直到所有的頂點都 進入了生成樹為止，此時的生成樹 就是最小生成樹

4. 普里姆演算法的普里姆演算法的實現

為了便於在兩個頂點集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無關，所以普里姆演算法特別適合於稠密圖求最小生成樹。

5. 普里姆演算法

可以這么理解：因為最小生成樹是包含所有頂點的所以開始lowcost先儲存到第一個點的所有值，然後執行下面演算法，找到最小值並記錄是第幾個點，比如說這個點是3，這樣有了一條1-3得道路已經確定，現在從3出發找從3出發到其他頂點的路徑，如果這個從3出發到達的路徑長度比從1出發的短，則更新lowcost，這樣使得lowcost保存一直到達該頂點的最短路徑。比如1-4是5，3-4是4，則lowcost從原來的5被改為4。

6. 什麼是普利姆演算法

Prim演算法：是圖的最小生成樹的一種構造演算法。

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

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

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

7. 最小生成樹 普里姆演算法和克魯斯卡爾演算法

kruskal演算法的時間復雜度主要由排序方法決定，其排序演算法只與帶權邊的個數有關，與圖中頂點的個數無關，當使用時間復雜度為O（eloge）的排序演算法時，克魯斯卡演算法的時間復雜度即為O（eloge），因此當帶權圖的頂點個數較多而邊的條數較少時，使用克魯斯卡爾演算法構造最小生成樹效果最好！

克魯斯卡爾演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾演算法構造最小生成樹的過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。

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

1.Kruskal
//題目地址:http://acm.pku.e.cn/JudgeOnline/problem?id=1258

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定義邊集
int cmp(const void *a,const void *b)//快排比較函數
{
return ((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v為點集
void makeset(int n)
{
for(int i=0;i<n;i++)
v[i]=i;
}
int find(int x)
{
int h=x;
while(h!=v[h])
h=v[h];
return h;
}
int main()
{
int n,i,j,r1,r2,p,total;
while(scanf("%d",&n)!=EOF)
{
p=0;
total=0;
makeset(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
e[p].v1=i;
e[p].v2=j;
e[p].len=a[i][j];
p++;
}
}
qsort(e,p,sizeof(e[0]),cmp);
for(i=0;i<p;i++)
{
r1=find(e[i].v1);
r2=find(e[i].v2);
if(r1!=r2)
{
total+=e[i].len;
v[r1]=r2;
}
}
printf("%d\n",total);
}
system("pause");
return 0;
}

2.Prim
//題目地址同上

#include <iostream>
using namespace std;

#define M 101
#define maxnum 100001
int dis[M][M];

int prim(int n)
{
bool used[M]={};
int d[M],i,j,k;
for(i=1; i<=n; i++)
d[i] = dis[1][i];
used[1] = true;
int sum=0;
for(i=1; i<n; i++){
int temp=maxnum;
for(j=1; j<=n; j++){
if( !used[j] && d[j]<temp ){
temp = d[j];
k = j;
}
}
used[k] = true;
sum += d[k];
for(j=1; j<=n; j++){
if( !used[j] && dis[k][j]<d[j] )
d[j] = dis[k][j]; // 與Dijksta演算法的差別之處
}
}
return sum;
}

int main()
{
int n,i,j;
while( cin>>n ){

for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d",&dis[i][j]);
if( !dis[i][j] )
dis[i][j] = maxnum;
}
}

cout<<prim(n)<<endl;
}
return 0;
}

代碼來自網路

8. 普里姆演算法生成最小代價生成樹有沒有可能超過一種就比如貪心選擇時最小權值有兩個或以上的時候如圖，

是的，最小生成樹的權值和是唯一的，但是最小生成樹本身不唯一。不管它是用哪種演算法計算的。

9. pascal普里姆演算法

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）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
採用堆可以將復雜度降為O(m log n)，如果採用Fibonaci堆可以將復雜度降為O(n log n + m)

10. 利用普里姆演算法求解最小生成樹，寫出步驟或畫圖表示過程。

<1,6>邊長度未知，這里看成無窮大。
歷次循環中，選擇兩端點分別在U，V中的邊中長度最小者，
具體如下：
1. 將1加入U中，其餘點加入V中。
2. 選擇邊<1,7>，將7加入U中，從V中除去該點。
3. 選擇邊<7,6>，將6加入U中，從V中除去該點。
4. 選擇邊<1,2>，將2加入U中，從V中除去該點。
5. 選擇邊<2,3>，將3加入U中，從V中除去該點。
6. 選擇邊<2,4>，將4加入U中，從V中除去該點。
7. 選擇邊<2,5>，將5加入U中，從V中除去該點。
結束。由上述六條邊組成的樹為求得的最小生成樹。