當前位置:首頁 » 操作系統 » prim演算法的實現

prim演算法的實現

發布時間: 2023-06-04 21:49:06

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

㈡ 普里姆演算法

你要先明白prim演算法的原理,明白原理後看下面的程序要點:

1.程序實現的時候將點分成兩部分,加入集合的和沒有加入集合的;
2.每次從沒有加入集合中找點;
3.對所有沒有加入到集合中的點中,找一個邊權最小的;
4.將邊權最小的點加入集合中,並且修改和加入點相連的沒有加入的點的權,重復第2步,知道所有的點都加入到集合中;

㈢ Python中prim演算法或kruscal演算法的實現

kruskal:
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define MAXE 100 //MAXE為最大的邊數
struct edges
{
int bv,tv,w; //邊集類型,存儲一條邊的起始頂點bv、終止頂點tv和權w
}edges;
typedef struct edges edgeset[MAXE];
//尋找v所在的連通集
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0)

i=set[i];
return i;
}
void kruskal(edgeset ge,int n,int e)
{
int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0;
i=1; //i表示待獲取的生成樹中的邊數,初值為1
j=1; //j表示ge中的下標,初值為1
while(j<n&&i<=e)//按邊權遞增順序,逐邊檢查該邊是否應加入到生成樹中
{
v1=seeks(set,ge[i].bv); //確定頂點v所在的連通集
v2=seeks(set,ge[i].tv);
cout<<ge[i].bv<<":"<<v1<<", "<<ge[i].tv<<":"<<v2<<endl;
if(v1!=v2) //當v1,v2不在同一頂點集合,確定該邊應當選入生成樹
{
cout<<"("<<ge[i].bv<<", "<<ge[i].tv<<") "<<ge[i].w<<endl;
set[v1]=v2;
j++;
}
i++;
}
}
int main()
{
edgeset ee;
int n,e; //n是圖的結點數,e是圖的邊數
n=6;
e=3;
for(int i=1;i<=e;i++)
{
scanf_s("%d",&ee[i].bv);
scanf_s("%d",&ee[i].tv);
scanf_s("%d",&ee[i].w);
}
//ee表示的邊集圖是按權值從小到大排列的
printf("最小生成樹邊集及它的權值: \n");
kruskal(ee,n,e);
system("pause");
return 0;
}
prim:

#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define N 3
void prim(int c[N][N])
{
//lowcost 為頂點間的最小距離,closest為最小距離上的鄰接頂點
//lowcost[i]:與頂點i連通的最小邊的權值
//closest[i]:與頂點i連通的鄰接頂點
int lowcost[N],closest[N];
int i,j,k,min;

//lowcost,closest初始化
for(i=0;i<N;i++)
{
lowcost[i]=c[0][i];
closest[i]=0;
}
closest[0]=-1;

//尋找U 和 V 之間連接的最短距離的鄰接點
for(i=0;i<N;i++)
{
min=32767;
k=0;
//尋找U 和 V 之間連接的最短距離的鄰接點
for(j=0;j<N;j++)
{
if((lowcost[j]<min)&&(closest[j]!=-1))
{
min=lowcost[j];
k=j;
}
}
//輸出新的鄰接頂點,並修改lowcost值
if(k)
{
cout<<"("<<closest[k]<<", "<<k<<") "<<lowcost[k]<<endl;
closest[k]=-1;
for(j=1;j<N;j++)
{
if(closest[j]!=-1)// huo if(!(closest[j]==-1))
{
//修改lowcost值
lowcost[j]=c[k][j];
//修改鄰接頂點
closest[j]=k;
}
}
}
}
}

int main()
{
int i,j,a[3][3];
cout<<"請輸入二維數組:"<<endl;
for(i=0;i<3;i++)

for(j=0;j<3;j++)

cin>>a[i][j];
cout<<"最小樹的結構為:"<<endl;
prim(a);
int q;
cin>>q;
return 0;
}

㈣ prim演算法是什麼

prim演算法是:圖論中的一種演算法。

普里姆演算法(Prim演算法),圖論中的一種演算法,可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中,不但包括了連通圖里的所有頂點(英語:Vertex (graph theory)),且其所有邊的權值之和亦為最小。

該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克(英語:Vojtěch Jarník)發現;並在1957年由美國計算機科學家羅伯特·普里姆(英語:Robert C. Prim)獨立發現;1959年,艾茲格·迪科斯徹再次發現了該演算法。因此,在某些場合,普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆-亞爾尼克演算法。

通過鄰接矩陣圖表示的簡易實現中,找到所有最小權邊共需O(V)的運行時間。使用簡單的二叉堆與鄰接表來表示的話,普里姆演算法的運行時間則可縮減為O(ElogV),其中E為連通圖的邊數,V為頂點數。如果使用較為復雜的斐波那契堆,則可將運行時間進一步縮短為O(E+VlogV),這在連通圖足夠密集時(當E滿足Ω(VlogV)條件時),可較顯著地提高運行速度。

㈤ 對給定的網和起點,實現求解最小生成樹的PRIM演算法,並給出動態演示。萬分火急

最近忙著考試,沒時間做圖形界面來動態演示部分啦,先給你一個基本的Prim程序吧,希望有所幫助。
/**
* PRIM(簡單版) 最小生成樹演算法 (Minimum Spanning Tree)
* 輸入:圖g; // 有向圖或者無向圖
* 輸出:(1)最小生成樹長sum;
* (2)最小生成樹prev。
* 結構: 圖g用鄰接矩陣表示,最短邊長dist用數組表示。
* 演算法:Prim演算法
* 復雜度:O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n; // n : 頂點個數
vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示)
vector<bool> known; // known : 各點是否已經選取
vector<早擾int> dist; // dist : 已選取點集到凳枯未選取點的最小邊長
vector<int> prev; // prev : 最小生成樹中各點的前一頂點
int s; // s : 起點(start)
int sum; // sum : 最小生成樹長

bool Prim() // 貪心演算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化起點到自身的路徑長為0。
int i;
for (i = 0; i < n; ++i)
{
int min = INT_MAX, v;
for (int i = 0; i <陸粗旦 n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 尋找未知的最短路徑長的頂點v,
if (min == INT_MAX) break; // 如果找不到,退出;
known[v] = true; // 如果找到,將頂點v設為已知,
sum += dist[v]; // 調整最小生成樹長
for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點w,
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; /* 調整頂點w的最短路徑長dist和最短路徑的前一頂點 prev。 */
}
return i == n; // 如果選取頂點個數為n,成功。
}

int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;
g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
g[4][6] = g[6][4] = 6;
g[5][6] = g[6][5] = 1;

s = 0; // 起點任選
sum = 0;
if (Prim())
{
cout << sum << endl;
for (int i = 1; i < n; ++i)
if(i != s) cout << prev[i] << "->" << i << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}

system("pause");
return 0;
}

㈥ 普里姆演算法的普里姆演算法的實現

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

㈦ 急!數據結構最小生成樹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;
}
}
}

熱點內容
linuxc語言文件讀寫 發布:2024-03-28 15:59:57 瀏覽:578
點遍歷演算法 發布:2024-03-28 15:57:34 瀏覽:496
java網路框架 發布:2024-03-28 15:42:07 瀏覽:98
我的世界本地部署伺服器 發布:2024-03-28 15:40:55 瀏覽:166
電腦代理伺服器認證 發布:2024-03-28 15:19:17 瀏覽:409
sql查詢當天數據 發布:2024-03-28 14:45:19 瀏覽:299
phpapi圖片 發布:2024-03-28 14:28:56 瀏覽:616
編程趣味 發布:2024-03-28 14:20:52 瀏覽:972
腳本文件編程 發布:2024-03-28 14:20:52 瀏覽:676
查詢資料庫實例名 發布:2024-03-28 14:20:45 瀏覽:680