當前位置:首頁 » 操作系統 » prim演算法時間復雜度

prim演算法時間復雜度

發布時間: 2022-06-23 15:23:40

A. 和Kruskal求最小生成樹的時間各為多少

設無向聯通圖的頂點n個,邊數e
Prim演算法時間復雜度為O(n^2)
Kruskal演算法時間復雜度是O(e*log2(e))

B. 利用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)圖用鄰接陣表示,路徑不通用無窮大表示,在計算機中可用一個大整數代替。
{先選定一個點,然後從該點出發,與該點相連的點取權值最小者歸入集合,然後再比較在集合中的兩點與其它各點的邊的權值最小者,再次進入集合,一直到將所有的點都歸入集合為止。}

C. prim演算法與kruskal演算法時間復雜度哪個小

令到圖中所有節點都連通的最小代價.就是最小生成樹
簡單點說
有幾個城市
你要設計一個路線 這個路線能走完所有的這幾個城市 而且路程最短
這個路線就是最小生成樹的含義

D. Prim和Dijkstra演算法的區別

在圖論中,Prim演算法是計算最小生成樹的演算法,而Dijkstra演算法是計算最短路徑的演算法。二者看起來比較類似,因為假設全部頂點的集合是V,已經被挑選出來的點的集合是U,那麼二者都是從集合V-U中不斷的挑選權值最低的點加入U。
二者的不同之處在於「權值最低」的定義不同,Prim的「權值最低」是相對於U中的任意一點而言的,也就是把U中的點看成一個整體,每次尋找V-U中跟U的距離最小(也就是跟U中任意一點的距離最小)的一點加入U;而Dijkstra的「權值最低」是相對於v0而言的,也就是每次尋找V-U中跟v0的距離最小的一點加入U。

一個可以說明二者不等價的例子是有四個頂點(v0, v1, v2, v3)和四條邊且邊值定義為(v0, v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的圖,用Prim演算法得到的最小生成樹中v0跟v1是不直接相連的,也就是在最小生成樹中v0v1的距離是v0->v2->v3->v1的距離是27,而用Dijkstra演算法得到的v0v1的距離是20,也就是二者直接連線的長度。

E. 最小生成樹兩種演算法有何區別

主要有兩個:
1.普里姆(Prim)演算法

特點:時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾(Kruskal)演算法

特點:時間復雜度為O(eloge)(e為網中邊數),適合於求稀疏的網的最小生成樹。

F. 數據結構 對於含有n個頂點e條邊的連通圖,利用Prim演算法求最小生成樹的時間復雜度為( ),利用K

O(n^2), O(elog2e)
求這兩個結果的過程任何一本比較全面的數據結構教科書上都有的

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

}

H. 在圖採用鄰接表存儲時prim演算法的時間復雜度

鄰接表儲存時,是B.鄰接矩陣儲存就是C了.

I. prim演算法 復雜度

普里姆演算法(Prim演算法),圖論中的一種演算法,可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中,不但包括了連通圖里的所有頂點,且其所有邊的權值之和亦為最小。該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克發現;並在1957年由美國計算機科學家羅伯特·普里姆獨立發現;1959年,艾茲格·迪科斯徹再次發現了該演算法。因此,在某些場合,普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆-亞爾尼克演算法。
演算法簡單描述
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來描述所得到的最小生成樹。
時間復雜度
這里記頂點數v,邊數e
鄰接矩陣:O(v2) 鄰接表:O(elog2v)

J. 採用鄰接表存儲,Prim演算法的時間復雜度是多少

設連同網中有n個定點,第一個進行初始化循環語句需要執行n-1次,第二個循環共執行n-1次,內嵌兩個循環,其一是在長度為n的數組中求最小值,需要執行n-1次,其二是條用輔助數組,需要執行n-1次。所以Prim演算法的復雜度是n*n

熱點內容
微信不記得密碼手機換號了怎麼辦 發布:2022-07-05 14:02:45 瀏覽:533
伺服器訪問不了網站 發布:2022-07-05 14:02:11 瀏覽:31
sql返回值的存儲過程 發布:2022-07-05 13:58:58 瀏覽:230
管理linux文件 發布:2022-07-05 13:58:50 瀏覽:747
詛咒密碼聲望是哪裡的 發布:2022-07-05 13:57:44 瀏覽:918
材料壓縮 發布:2022-07-05 13:57:37 瀏覽:786
安卓山寨機怎麼刷機 發布:2022-07-05 13:55:26 瀏覽:87
win7系統ftp伺服器 發布:2022-07-05 13:49:01 瀏覽:627
瑞納安卓導航大屏哪個牌子好 發布:2022-07-05 13:46:10 瀏覽:30
php批量插入數據 發布:2022-07-05 13:44:33 瀏覽:598