導航:首頁 > 源碼編譯 > prim演算法的證明

prim演算法的證明

發布時間:2023-10-06 01:50:39

A. 普里姆演算法

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

B. 什麼是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;

}

C. 誰能幫我畫個PRIM演算法的流程圖

對於這種比較高級的演算法代碼直接看程序會比較蒙,你就光看我的演算法流程吧,prim演算法用的是貪心演算法的思想,即每一步都作出局部的最優解,關於prim演算法為什麼能用貪心演算法的證明,你可以參考《計算機演算法設計與分析》這本書。(我反正不想看那麼無聊的證明,也看不明白,呵呵)。
定義一個集合v 和 a,其中v是全體節點(總節點數為n)的集合,v初始為空。定義一個記錄最小生成數邊數的變數c。
1.在v中任選一個節點,並加入到a中。在v中刪除該節點。

2.選一個在所有連接v集合和a集合權值最小的邊(即一個節點是v的某一個節點,一個是a中的某一個節點)

3。將兩個節點連接。將c加1

4.將第3步才在v中節點刪除並加入到a中.

5.如果c為n-1則完成最小生成樹,否則回到第2步。

明白了沒?不明白再問我啊,希望對你有所幫助。

D. 什麼是普利姆演算法

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

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

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

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

E. Prim 演算法和 Kruskal 演算法

1).輸入:一個加權連通圖,其中頂點集合為V,邊集合為E;

2).初始化:Vnew = {x},其中x為集合V中的任一節點(起始點),Enew = {},為空;

3).重復下列操作,直到Vnew = V:

a.在集合E中選取權值最小的邊<u, v>,其中u為集合Vnew中的元素,而v不在Vnew集合當中,並且v∈V(如果存在有多條滿足前述條件即具有相同權值的邊,則可任意選取其中之一);

b.將v加入集合Vnew中,將<u, v>邊加入集合Enew中;

4).輸出:使用集合Vnew和Enew來描述所得到的最小生成樹。

反證法 :假設prim生成的不是最小生成樹

1).設prim生成的樹為G0

2).假設存在Gmin使得cost(Gmin)<cost(G0) 則在Gmin中存在<u,v>不屬於G0

3).將<u,v>加入G0中可得一個環,且<u,v>不是該環的最長邊(這是因為<u,v>∈Gmin)

4).這與prim每次生成最短邊矛盾

5).故假設不成立,命題得證.

1).記Graph中有v個頂點,e個邊

2).新建圖Graphnew,Graphnew中擁有原圖中相同的e個頂點,但沒有邊

3).將原圖Graph中所有e個邊按權值從小到大排序

4).循環:從權值最小的邊開始遍歷每條邊 直至圖Graph中所有的節點都在同一個連通分量中
如果這條邊連接的兩個節點於圖Graphnew中不在同一個連通分量中,添加這條邊到圖Graphnew中

歸納基礎:

n=1,顯然能夠找到最小生成樹。

歸納過程:

假設Kruskal演算法對n≤k階圖適用,那麼,在k+1階圖G中,我們把最短邊的兩個端點a和b做一個合並操作,即把u與v合為一個點v',把原來接在u和v的邊都接到v'上去,這樣就能夠得到一個k階圖G'(u,v的合並是k+1少一條邊),G'最小生成樹T'可以用Kruskal演算法得到。

我們證明T'+{<u,v>}是G的最小生成樹。

用反證法,如果T'+{<u,v>}不是最小生成樹,最小生成樹是T,即W(T)<W(T'+{<u,v>})。顯然T應該包含<u,v>,否則,可以用<u,v>加入到T中,形成一個環,刪除環上原有的任意一條邊,形成一棵更小權值的生成樹。而T-{<u,v>},是G'的生成樹。所以W(T-{<u,v>})<=W(T'),也就是W(T)<=W(T')+W(<u,v>)=W(T'+{<u,v>}),產生了矛盾。於是假設不成立,T'+{<u,v>}是G的最小生成樹,Kruskal演算法對k+1階圖也適用。

由數學歸納法,Kruskal演算法得證。

F. cs61b實驗記錄(三)project 2 prim迷宮隨機生成演算法

nothing special

具體詳見我的GitHub: https://github.com/BoL0150/Berkeley-cs61b/tree/main/hw1

Random對象是一個「偽隨機數」生成器,它可以產生一串無窮的看起來是隨機數的數字序列,調用nextInt方法獲取序列中的每一個數字。

它之所以叫「偽隨機數」是因為它產生的序列並不是真正隨機的。我們獲取不同的序列的方式是向Random的構造器中傳入一個數字,這個數字被稱為「seed」,如果我們用相同的seed構造Random,那麼我們一定會獲得完全相同的序列。

java.lang.Math中也有一個名為random()的靜態方法可以生成隨機數

Math.random() 方法生成[0, 1)范圍內的double類型隨機數;Random類中的nextXxxx(n)系列方法生成0(包括)到n(不包括)之間的隨機數;

繪制地圖:

從宏觀上來看,主要分為這么幾步:

創建一個Room類,將每一個房間當作一個對象,隨機生成房間的坐標以及長和寬,然後判斷房間是否重疊,

同時設置一個參數,控制房間重復生成的上限次數。 將所有生成的房間對象放在一個List中 ,因為在修建完迷宮後還需要對每一個房間與它旁邊的迷宮進行打通,以便獲取房間的位置和參數。

此時在房間中填GRASS以及使用兩個數組的原因稍後進行解釋。

我們將這一步分解來看,首先:如何在一張空的圖上生成迷宮?

我們採用 prim迷宮隨機生成演算法 ,此演算法的原理及具體實現如下:

原理:

具體實現:

生成迷宮時要注意 隨機 從候選列表中選取點,否則生成的迷宮會朝著同一個方向

我們知道了如何在空的圖上生成迷宮,也可以由此推斷出如何在房間的周圍生成迷宮

這一步沒什麼好說的,對每一個房間隨機選取一條邊上的一點向外打通,如果不符合條件(如碰到NOTHING等)就重新選取一點。

然而,此時的圖中還有很多的死胡同(即三面都是牆的FLOOR),以及房間中依然是GRASS,所以我們需要填補所有的死胡同,將GRASS替換為FLOOR。

去除死胡同我們需要對每一個點,查看周圍的四個點是否是WALL,然後改變這個點,再進入下一個點。這會讓人想起DFS,但是原本的DFS是沿著一條路線,從一頭走到另一頭,對路上的每一個點都只是 依次 查看周圍的點,一旦找到可以通過的點,就立馬進入, 無法確定這一點周圍是否有3個WALL 。只有當走到頭時,掃描了周圍的四個點,發現都無法通過,才會往後退。也就是說,只有後退的時候,我們才能知道某一點周圍所有點的情況。而填補所有的死胡同需要我們從所有的死胡同的終點出發,向中間匯聚,一邊移動一邊填補。

所以我們需要將DFS改造成 前進和後退時都要查看周圍所有點的情況 ,才能進行下一步。

我們還需要移除所有多餘的牆,也就是四個角上沒有FLOOR的WALL

最後,再添加上Player和Lock_Door就完成了

附上autograder的評分

閱讀全文

與prim演算法的證明相關的資料

熱點內容
魔獸鍵位設置命令宏 瀏覽:645
程序員沒有目標了 瀏覽:828
搶答器c程序編程 瀏覽:703
什麼app可以自己玩 瀏覽:76
刨客app是什麼 瀏覽:963
cad輸入命令欄不見了 瀏覽:834
做故事集可以用什麼app 瀏覽:692
qq郵箱發送壓縮包 瀏覽:672
程序員桌面機器人 瀏覽:589
xjr快速開發平台源碼 瀏覽:159
java介面runnable 瀏覽:31
python怎麼運行web伺服器 瀏覽:349
notepad編程代碼 瀏覽:740
什麼安卓的毛病最少 瀏覽:611
hp的pjl設備訪問命令 瀏覽:635
googlewebp圖片壓縮技術 瀏覽:215
tbc薩滿加血宏命令 瀏覽:757
pdf閃 瀏覽:289
手機伺服器地址填什麼 瀏覽:258
lrpython代碼 瀏覽:848