導航:首頁 > 源碼編譯 > kruskal演算法復雜度

kruskal演算法復雜度

發布時間:2023-04-06 03:12:31

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

❷ 蟻群演算法中轉移概率是怎麼用的.不同的螞蟻為什麼會選擇不同的路徑

因為不同路徑的信息素和啟發信息不同,所以向每條路徑轉移的概率也不同;
具體實現可以運用輪盤賭選擇,轉移概率越大的路徑就會有更多的螞蟻選擇.。
Prime 演算法和 Kruskal 演算法都是用來求加權連通簡單圖中權和最小的支撐樹(即最小樹)的,Prime演算法的時間復雜度為O(n^2) (n 為耐仿慎頂點數),Kruskal 演算法的時間復雜度為 O(eln(e)) (e為邊數),這兩種演算法都昌敬是多項式時間演算法,也就是說,最小樹問題已經有了有效演算法去求解,屬於P問題。
Dijkstra 演算法求解的是加權連通簡單圖中一個頂點到其它每個頂點的具有最小權和的有向路,最簡單版本的時間復雜度是O(n^2),也是多項式時間演算法。
而蟻群演算法是一種近似算大橘法,它不是用來解決已存在精確有效演算法的問題的,而是用來解決至今沒有找到精確的有效演算法的問題的,比如旅行商問題(TSP)。
旅行商問題也可以說是求「最短路徑」,但它是求一個完全圖的最小哈密頓圈,這個問題至今未找到多項式時間演算法,屬於NPC問題,也就是說,當問題規模稍大一點,現有的精確演算法的運算量就會急劇增加。
文中的某些觀點引自知乎大神余幸恩,感謝幫忙!~

❸ c加加提問,克魯斯卡爾演算法是什麼

克魯斯卡爾演算法,從邊的角度求網的最小生成樹,時間復雜度為O(eloge)。和普里姆演算法恰恰相反,更適合於求邊稀疏的網的最小生成樹。

對於任意一個連通網的最小生成樹來說,在要求總的權值最小的情況下,最直接的想法就是將連通網中的所有邊按照權值大小進行升序排序,從小到大依次選擇。

由於最小生成樹本身是一棵生成樹,所以需要時刻滿足以下兩點:

❹ 求最小生成樹 利用Kruskal演算法求圖G的一棵最小生成樹T,用c語言

#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 並查集存儲結返賣構
// Tags: 值為-1則表示為根節點
struct DisjointSet
{
int *arr;// 值為父節點下標
int number;// arr元素個數
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化並查集結構
// Input: number - 元素的個數
// Output:s - number個元素自成一集的並查集
void InitSet(DisjointSet &s, int number)
{
s.number = number;
s.arr = new int[number];
memset(s.arr, -1, sizeof(int) * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 刪除並查集結構
// Input: s - 並查集存儲結構
// Output:s - 回收內存後的結構
void FreeSet(DisjointSet &s)
{
if (s.arr)
{
delete []s.arr;
s.number = 0;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 獲得某個結點的根節點
// Input: s - 並查集; index - 結點下標
// Output: return - 根節點下標
int GetRoot(DisjointSet &s, int index)
{
while (s.arr[index] != -1)
index = s.arr[index];

return index;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 合並index1和index2所在的兩個集合
// Input: index1 - 結點1下標, index2 - 結點2下標
// Output: s - 並查集
void Union(DisjointSet &s, int index1, int index2)
{
int root1 = GetRoot(s, index1);
int root2 = GetRoot(s, index2);

s.arr[root1] = root2;
}

////////////////////////////////////////////////////////////////////////////////////////漏拆逗///////////////////////////////
// Description: 判斷兩個結點是否在同一個集合中
// Input: s - 並查集, index1 - 結點1下標, index2 - 結點2下標
// Output: return - true: 在 false: 不在
bool Find(DisjointSet &s, int index1, int index2)
{
return GetRoot(s, index1) == GetRoot(s, index2);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 圖的鄰接矩陣
struct Graph
{
int **value;// 權值,-1表示無法到達
int number;
};

/////////////御陪//////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化一個圖
// Input: g - 圖的存儲結構, number - 結點個數
// Output: g - 圖
void InitGraph(Graph &g, int number)
{
int i = 0;

g.value = new int *[number];
for (i = 0; i < number; i++)
g.value[i] = new int[number];

g.number = number;
memset(*g.value, -1, sizeof(int) * number * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 回收一個圖
// Input: g - 圖, number - 結點個數
// Output: g - 圖的存儲結構
void FreeGraph(Graph &g)
{
int i = 0;

for (i = 0; i < g.number; i++)
delete []g.value[i];

delete []g.value;

g.value = 0;
g.number = 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 為圖在a,b間添加一條邊
// Input:e1, e2 - 兩個結點, value - 權值
// Output: graph - 加邊後的圖
void AddEdge(Graph &graph, int e1, int e2, int value)
{
graph.value[e1][e2] =value;
graph.value[e2][e1] = value;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 顯示一條邊
struct OneEdge
{
OneEdge(int _a = 0, int _b = 0, int _value = 0):
a(_a), b(_b), value(_value){}

int a, b;// 邊的兩個結點
int value; // 邊的權值
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 根據權值判斷兩個邊的大小
// Tags: 由於priority_queue是最大堆,所以這里小於號變成大於號,從而使priority_queue變成最小堆
bool operator <(OneEdge e1, OneEdge e2)
{
if (e1.value > e2.value) return true;
else return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用戶輸入圖的邊
// Input: n - 加邊的個數
// Output: graph - 加邊後的圖
// Tags: Console下用戶輸入點對(a, b, v)
void InputEdge(Graph &graph, int n)
{
int i = 0, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &a, &b, &v);
AddEdge(graph, a, b, v);
}
}

int main()
{
const int NODE_NUMBER = 6;
const int EDGE_NUMBER = 9;

Graph graph;// 圖
DisjointSet set;// 並查集
priority_queue<OneEdge> edge;// 2叉堆

InitGraph(graph, NODE_NUMBER);// 初始化圖
InputEdge(graph, EDGE_NUMBER);
InitSet(set, NODE_NUMBER); // 初始化並查集

int i = 0, j = 0;// 初始化堆
for (i = 0; i < NODE_NUMBER; i++)
for (j = i; j < NODE_NUMBER; j++)
if (graph.value[i][j] > 0)
edge.push(OneEdge(i, j, graph.value[i][j]));

int min_pay = 0;// 最小耗費值
int add_num = 0;// 已經添加了幾個邊
OneEdge min_value_edge;// 當前權值最小邊

while (add_num < NODE_NUMBER - 1)
{
min_value_edge = edge.top();
// 這里是因為了STL中2叉堆的結構中有一個緩沖區
// 需要將緩沖區中的每一個元素彈出來
if(min_value_edge.value > 0 && !Find(set, min_value_edge.a, min_value_edge.b))
{
Union(set, min_value_edge.a, min_value_edge.b);
min_pay += min_value_edge.value;
add_num++;
}
edge.pop();
}

printf("%d", min_pay);
return 0;
}

這個是c++語言的,最小權值存儲在min_pay中,樹存儲在並查集set中,且在獲取最小權值路徑的時候用了STL中的2叉堆,演算法復雜度為O(|V| * lgE)
不知是否滿足您的要求

❺ Prim演算法和Kruskal演算法的空間復雜度

O(n^2)

❻ kruskal演算法是什麼

kruskal演算法是:克魯斯卡爾演算法。禪緩是求連通網的最小生成樹的另一種方法。與普里姆演算法不同,它的時間復雜度為O(eloge)、(e為網中的邊數)租襲野,所以,適合於求邊稀疏的網的最小生成樹。

克魯斯卡爾(Kruskal)演算法從另一途徑求網的最小生成樹。其基本思想是:假設連通網G=(V,E),令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=(V,{}),概述圖中每個頂點自成一個連通分量。

在E中選擇代價最小的邊,若該邊依附的頂點分別在T中不同的連通分量上,則將此邊加入到T中;否則,捨去此邊而選擇下一條代價最小的邊。依此類推,直至T中所有頂點構成一個連通分量為止。

復雜度:

克魯斯卡爾演算法的時間復雜度主要由排序方法決定,而克魯斯卡爾演算法的排序方法只與網中邊的條數有關,而與網中頂點的個數無關,當使用時間復雜度為O(elog2e)的排序方法時,克魯斯卡爾演算法的時間復雜度即為O(log2e),因此當網的頂點個數較多、而邊的條數較少時,使用克魯斯卡爾演算法構造最小生成弊喊樹效果較好。

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

主要有兩個:
1.普里姆(prim)演算法
特點:時間復雜度為御老o(n2).適合於求邊稠密鎮森升的最小生成樹。
2.克魯斯卡爾(kruskal)演算法
特點:時間復雜度為o(eloge)(e為網中邊數),適合於春蔽求稀疏的網的最小生成樹。

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

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

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

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

❾ 克魯斯卡爾時間復雜度怎麼算出來的

Kruskal演算法的時間復雜度由排序演算法決定,若採用快排則時間復雜度為O(N log N)。

kruskal演算法:

求加權連通圖的最小生成樹的演算法。kruskal演算法總共選擇n- 1條邊,(共n個點)所使用的貪婪准則是:從剩下的邊中選擇一條不會產生環路的
具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。kruskal演算法分e 步,其中e
是網路中邊的數目。按耗費遞增的順序來考慮這e
條邊,每次考慮一條邊。當考慮某條邊時,若將其加入到已選邊的集合中會出現環路,則將其拋棄,否則,將它選入。
假設WN=(V,{E})是一個含有 n 個頂點的連通網,則按照克魯斯卡爾演算法構造最小生成樹的
過程為:先構造一個只含 n 個頂點,而邊集為空的子圖,若將該子圖中各個頂點看成是各棵樹上的根結點,則它是一個含有 n
棵樹的一個森林。之後,從網的邊集 E
中選取一條權值最小的邊,若該條邊的兩個頂點分屬不同的樹,則將其加入子圖,也就是說,將這兩個頂點分別所在的兩棵樹合成一棵樹;反之,若該條邊的兩個頂
點已落在同一棵樹上,則不可取,而應該取下一條權值最小的邊再試之。依次類推,直至森林中只有一棵樹,也即子圖中含有 n-1條邊為止。

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

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;
}

代碼來自網路

閱讀全文

與kruskal演算法復雜度相關的資料

熱點內容
單片機的功能模塊 瀏覽:771
安卓手機如何錄制視頻長時間 瀏覽:285
安全問題app哪個好 瀏覽:445
壓縮水會變冰嗎 瀏覽:526
小說配音app哪個靠譜 瀏覽:820
編譯iso 瀏覽:944
照片生成pdf格式 瀏覽:194
病歷轉pdf 瀏覽:835
雲伺服器配硬體 瀏覽:978
伺服器10k什麼意思 瀏覽:21
pdfeditor漢化 瀏覽:884
新科學pdf 瀏覽:746
現在還有c語言編譯嗎 瀏覽:675
哪裡買到單片機 瀏覽:480
linux文件打開數量 瀏覽:510
編譯原理中什麼是l屬性文法 瀏覽:372
硬碟加密時出現的問題 瀏覽:61
如何退域命令 瀏覽:108
看書的app哪裡看 瀏覽:291
伺服器怎麼調大 瀏覽:4