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（普里姆）演算法 構造最小生成樹 程序
演算法同樣是解決最小生成樹的問題。
其演算法為：在這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）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
{先選定一個點，然後從該點出發，與該點相連的點取權值最小者歸入集合，然後再比較在集合中的兩點與其它各點的邊的權值最小者，再次進入集合，一直到將所有的點都歸入集合為止。}
Ⅲ 已知一個無向圖如下，分別用普里姆和克魯斯卡爾演算法生成最小生成樹（假設以1為起點，試畫出構造過程）。
1)普里姆演算法思想
從圖中任意取出一個頂點， 把它當成棵樹，然後從與這棵樹相接的邊中選取一條最短(權值最小)的邊， 並將這條邊及其所連接的頂點也並入這棵樹中，此時得到了一棵有兩個頂點的樹。然後從與這棵樹相接的邊中選取一條最短的邊，並將這條邊及其所連頂點並入當前樹中，得到一棵有3個頂點的樹。以此類推，直到圖中所有頂點都被並入樹中為止，此時得到的生成樹就是最小生成樹。
2)克魯斯卡爾演算法思想
先將邊中的權值從小到大排序，每次找出候選邊中權值最小的邊，就將該邊並入生成樹中。重復此過程直到所有邊都被檢測完為止。其中要注意的是克魯斯卡爾演算法需要用到並查集，以此來判斷接下來要並入的邊是否會和已並入的邊構成迴路。這兩個圖分別用普里姆和克魯斯卡爾生成的最小生成樹見圖。
需要注意的是，在接下來要並入的最小權值不唯一的情況下，可以選取的邊是不唯一的，所以其最小生成樹也不唯一。(純手打，望採納，謝謝。)
Ⅳ 最小生成樹
所謂最小生成樹，就是在一個具有N個頂點的帶權連通圖G中，如果存在某個子圖G'，其包含了圖G中的所有頂點和一部分邊，且不形成迴路，並且子圖G'的各邊權值之和最小，則稱G'為圖G的最小生成樹。 由定義我們可得知最小生成樹的三個性質：
•最小生成樹不能有迴路。
•最小生成樹可能是一個，也可能是多個。
•最小生成樹邊的個數等於頂點的個數減一。宴昌 本文將介紹兩種最小生成樹的演算法，分別為克魯斯卡爾演算法(Kruskal Algorithm)和普利姆演算法(Prim Algorithm)。
克魯斯卡爾演算法的核心思想是：在帶權連通圖中，不斷地在邊集合中找到最小的邊，如果該邊滿足得到最小生成樹的條件，就將其構造，直到最後得到一顆最小生成樹。
克魯斯卡爾演算法的執行步驟：
第一步：在帶權連通圖中，將邊的權值排序；
第二步：判斷是否需要選擇這條邊（此時圖中的邊已按權值從小到大排好序）。判斷的依據是邊的兩個頂點是亂蘆否已連通，如果連通則繼續下一條；如果不連通，那麼就選擇晌陪扒使其連通。
第三步：循環第二步，直到圖中所有的頂點都在同一個連通分量中，即得到最小生成樹。
下面我用圖示法來演示克魯斯卡爾演算法的工作流程，如下圖：
Ⅳ 簡述最小生成樹的Prime演算法的思想
因該是prim演算法
假設V是圖中頂點的集合,E是圖中邊的集合,TE為最小生成樹中的邊的集合,則prim演算法通過以下步驟可以得到最小生成樹:
1:初始化:U={u 0},TE={f}.此步驟設立一個只有結點u 0的結點集U和一個空的邊集TE作為最小生成樹的初始形態,在隨後的演算法執行中,這個形態會不斷的發生變化,直到得到最小生成樹為止.
2:在所有u∈U,v∈V－U的邊(u,v)∈E中,找一條權最小的邊(u 0,v 0),將此邊加進集合TE中,並將此邊的非U中頂點加入U中.此步驟的功能是在邊集E中找一條邊,要求這條邊滿足以下條件:首先邊的兩個頂點要分別在頂點集合U和V－U中,其次邊的權要最小.找到這條邊以後,把這條邊放到邊集TE中,並把這條邊上不在U中的那個頂點加入到U中.這一步驟在演算法中應執行多次,每執行一次,集合TE和U都將發生變化,分別增加一條邊和一個頂點,因此,TE和U是兩個動態的集合,這一點在理解演算法時要密切注意.
3:如果U=V,則演算法結束;否則重復步驟2.可以把本步驟看成循環終止條件.我們可以算出當U=V時,步驟2共執行了n－1次(設n為圖中頂點的數目),TE中也增加了n－1條邊,這n－1條邊就是需要求出的最小生成樹的邊.
Ⅵ 普里姆演算法是什麼
普里姆(Prim)演算法，和克魯斯卡爾演算法一樣，是用來求加權連通圖的最小生成樹的演算法。
普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。
該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；並在1957年由美國計算機科學家羅伯特·普里姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法。
基本思想：
對於圖G而言，V是所有頂點的集合；現在，設置兩個新的集合U和T，其中U用於存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。
從所有uЄU，vЄ(V-U) (V-U表示出去U的所有頂點)的邊中選取權值最小的邊(u, v)，將頂點v加入集合U中，將邊(u, v)加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，這時集合T中包含了最小生成樹中的所有邊。
Ⅶ 話說最小生成樹的prim演算法和kursual演算法的區別
prim演算法和kurskal演算法解決的問題是相同的，都用來求最小生成樹。從某一結點A出發，按照一定次序，經過中間結點集Q中的每一個結點，得到最短路徑，稱為最小生成樹。
kurskal演算法的核心思想就是「盡可能的選取短邊」，按照長度從小到大依次加入生成樹；prim演算法引入一個概念——生長點（和非生長點），每次加入的最短邊是與生長點相鄰的最短邊，初始狀態下，唯一的一個點就是生長點，隨著新邊的加入，每次加入的邊的末端就是生長點，若某一生長點已經沒有相鄰邊可以加入，就回溯到上一級結點，加入新邊，直到Q中的所有結點都加入圖中。
一般教材編的都很清楚的，結合我這個，再看看書，相信你很快就會明白的。
Ⅷ 已知圖G如下所示，根據Prim演算法，構造最小生成樹。（要求給出生成過程）
①將帶權連通圖G=的各邊按權從小到大依次排列，如e1,e2,…,em,其中e1的權最小，em的權最大，m為邊數。 ②取權最小的兩條邊構成邊集T0，即T0={e1,e2},從e3起，按次序逐個將各邊加進集合T0中去，若出現迴路則將這條邊排除（不加進去），按此法一直進行到em，最後得到n-1條邊的集合T0={e1,e2,…,en-1}，則T0導出的子圖就是圖G的最小生成樹。