克魯斯卡爾演算法

① 克魯斯卡爾演算法的時間復雜度為多少

時間復雜度為O(|E|log|E|)，其中E和V分別是圖的邊集和點集。

基本思想是先構造一個只含 n 個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹。

反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。

(1)克魯斯卡爾演算法擴展閱讀：

克魯斯卡爾演算法證明

假設G=(V,E) 是一個具有n個頂點的連通網，T=(U,TE)是G的最小生成樹，U的初值等於V，即包含有G中的全部頂點，TE的初值為空集。該演算法的基本思想是：將圖G中的邊按權值從小到大的順序依次選取。

若選取的邊使生成樹T不形成迴路，則把它並入TE中，保留作為T的一條邊，若選取的邊使生成樹T形成迴路，則將其舍棄，如此進行下去直到TE中包含n-1條邊為止，此時的T即為最小生成樹。

克魯斯卡爾演算法，至多對e條邊各掃描一次，每次選擇最小代價的邊僅需要O(loge)的時間。因此，克魯斯卡爾演算法的時間復雜度為O(eloge)。

② kruskal演算法

給每個子樹一個不同的編號，對每一個頂點引入一個標記t，表示這個頂點所在的子樹編號。當加入一條紅色邊，就會使該邊兩端點所在的兩個子樹連接起來，成為一個子樹，從而兩個子樹中的頂點標記要改變成一樣。綜上，可將Kruskal演算法細化使其更容易計算機實現。

kruskal應該是遞歸演算法吧，在定義圖中各端點時，可以多設一個標記，把圖遞歸遍歷一遍，在同一連同子圖上的點，標記為一樣的整型數值即可。

參考：http://ke..com/view/580403.htm

③ 克魯斯卡爾演算法的基本思想

先構造一個只含 n 個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。時間復雜度為為O(e^2), 使用並查集優化後復雜度為 O（eloge），與網中的邊數有關，適用於求邊稀疏的網的最小生成樹。

④ c加加提問，克魯斯卡爾演算法是什麼

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

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

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

• 生成樹中任意頂點之間有且僅有一條通路，也就是說，生成樹中不能存在迴路；

• 對於具有 n 個頂點的連通網，其生成樹中只能有 n-1 條邊，這 n-1 條邊連通著 n 個頂點。

連接 n 個頂點在不產生迴路的情況下，只需要 n-1 條邊。

• 所以克魯斯卡爾演算法的具體思路是：將所有邊按照權值的大小進行升序排序，然後從小到大一一判斷，條件為：如果這個邊不會與之前選擇的所有邊組成迴路，就可以作為最小生成樹的一部分；反之，捨去。直到具有 n 個頂點的連通網篩選出來 n-1 條邊為止。篩選出來的邊和所有的頂點構成此連通網的最小生成樹。



判斷是否會產生迴路的方法為：在初始狀態下給每個頂點賦予不同的標記，對於遍歷過程的每條邊，其都有兩個頂點，判斷這兩個頂點的標記是否一致，如果一致，說明它們本身就處在一棵樹中，如果繼續連接就會產生迴路；如果不一致，說明它們之間還沒有任何關系，可以連接。

• 假設遍歷到一條由頂點 A 和 B 構成的邊，而頂點 A 和頂點 B 標記不同，此時不僅需要將頂點 A 的標記更新為頂點 B 的標記，還需要更改所有和頂點 A 標記相同的頂點的標記，全部改為頂點 B 的標記。


（6）



• 當選取的邊的數量相比與頂點的數量小 1 時，說明最小生成樹已經生成。所以最終採用克魯斯卡爾演算法得到的最小生成樹為（6）所示。



• 實現代碼：#include "stdio.h"#include "stdlib.h"#define MAX_VERtEX_NUM 20#define VertexType inttypedef struct edge{VertexType initial;VertexType end;VertexType weight;}edge[MAX_VERtEX_NUM];//定義輔助數組typedef struct {VertexType value;//頂點數據int sign;//每個頂點所屬的集合}assist[MAX_VERtEX_NUM];assist assists;//qsort排序函數中使用，使edges結構體中的邊按照權值大小升序排序int cmp(const void *a,const void*b){return ((struct edge*)a)->weight-((struct edge*)b)->weight;}//初始化連通網void CreateUDN(edge *edges,int *vexnum,int *arcnum){printf("輸入連通網的邊數： ");scanf("%d %d",&(*vexnum),&(*arcnum));printf("輸入連通網的頂點： ");for (int i=0; i<(*vexnum); i++) {scanf("%d",&(assists[i].value));assists[i].sign=i;}printf("輸入各邊的起始點和終點及權重： ");for (int i=0 ; i<(*arcnum); i++) {scanf("%d,%d,%d",&(*edges)[i].initial,&(*edges)[i].end,&(*edges)[i].weight);}}//在assists數組中找到頂點point對應的位置下標int Locatevex(int vexnum,int point){for (int i=0; i<vexnum; i++) {if (assists[i].value==point) {return i;}}return -1;}int main(){int arcnum,vexnum;edge edges;CreateUDN(&edges,&vexnum,&arcnum);//對連通網中的所有邊進行升序排序，結果仍保存在edges數組中qsort(edges, arcnum, sizeof(edges[0]), cmp);//創建一個空的結構體數組，用於存放最小生成樹edge minTree;//設置一個用於記錄最小生成樹中邊的數量的常量int num=0;//遍歷所有的邊for (int i=0; i<arcnum; i++) {//找到邊的起始頂點和結束頂點在數組assists中的位置int initial=Locatevex(vexnum, edges[i].initial);int end=Locatevex(vexnum, edges[i].end);//如果頂點位置存在且頂點的標記不同，說明不在一個集合中，不會產生迴路if (initial!=-1&& end!=-1&&assists[initial].sign!=assists[end].sign) {//記錄該邊，作為最小生成樹的組成部分minTree[num]=edges[i];//計數+1num++;//將新加入生成樹的頂點標記全不更改為一樣的for (int k=0; k<vexnum; k++) {if (assists[k].sign==assists[end].sign) {assists[k].sign=assists[initial].sign;}}//如果選擇的邊的數量和頂點數相差1，證明最小生成樹已經形成，退出循環if (num==vexnum-1) {break;}}}//輸出語句for (int i=0; i<vexnum-1; i++) {printf("%d,%d ",minTree[i].initial,minTree[i].end);}return 0;}


• 測試數據：



輸入連通網的邊數：
6 10
輸入連通網的頂點：
1
2
3
4
5
6
輸入各邊的起始點和終點及權重：
1,2,6
1,3,1
1,4,5
2,3,5
2,5,3
3,4,5
3,5,6
3,6,4
4,6,2
5,6,6
1,3
4,6
2,5
3,6
2,3

⑤ 克魯斯卡爾演算法

哈哈，因為愛情。
parent數組裝的是每個連通分量的第一個開始點，最初的狀態有n個節點，n個分量，都是第一個，所以全都賦值0，而開始合並後，將一個個的分量逐步的合並到一起，parent記錄的就是父節點，一個聯通分量只有一個parent為0的。
而判斷循環是如果兩個的最終的開始節點是同一個，就說明你加上這條邊就形成循環了，這條邊就不能加

⑥ 克魯斯卡爾演算法 判斷迴路中的問題

看這段代碼真令我頭疼，我就告訴你思路吧！
並查集你會不會？如果會的話那就好辦。
kruskal演算法用到了一種貪心策略，首先要把邊集數組以邊的權值從小到大排序，然後一條邊一條邊的查找，如果邊的兩個端點不在一個集合內，則將此邊添加到正在生長的樹林中，並合並兩個端點所在的集合，直到最小生成樹已生成完畢。
核心偽代碼如下（本人不習慣給完整的可編譯的代碼）：
func root(x:longint):longint;//查找i節點所在集合
var i,j,k:longint;
{i:=x;j:=x;
while i!=f[i] do i=f[i];
while j!=i do
{k=j;j=f[j];f[k]=i;}//路徑壓縮，若不壓縮效率將很低
};//root
proc union(i,j,c:longint);
var x,y:longint;
{x=root(i);
y=root(j);
if x!=y then {inc(ans,c);inc(temp);f[y]=x;}
//若i和j分屬兩棵子樹，則將此邊添加到森林中，並合並其所在集合
};//union;
將邊集數組按照邊的權值從小到大排序;
for (i=1,i++,i=n) f[i]=i;//並查集初始化
for (i=1,i++,i=m)
{union(edge[i].x,edge[i].y,edge[i].z);
if temp==n-1 then break;
//若temp==n-1則最小生成樹已生成完畢，退出
}//kruskal
if temp==n-1 then writeln(ans)//輸出最小生成樹的權值和
else writeln('No solution!');//若temp!=n-1，則說明此圖為非連通圖

⑦ 克魯斯卡爾演算法是怎樣判斷是否構成了迴路

使用遍歷方法，同時存儲他們的父親節點，如果父親節點不一樣，就說明有迴路

⑧ 什麼是克魯斯卡爾演算法

設有一個有n個頂點的連通網N={V,E},最初先構造一個只有n個頂點，沒有邊的非連通圖T={V, E},圖中每個頂點自成一個連通分量。當在E中選到一條具有最小權值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中；否則將此邊捨去，重新選擇一條權值最小的邊。如此重復下去，直到所有頂點在同一個連通分量上為止。2演算法描述編輯克魯斯卡爾演算法的時間復雜度為O（eloge）(e為網中邊的數目)，因此它相對於普里姆演算法而言，適合於求邊稀疏的網的最小生成樹。克魯斯卡爾演算法從另一途徑求網的最小生成樹。假設連通網N=（V，{E}），則令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=（V，{∮}），圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則捨去此邊而選擇下一條代價最小的邊。依次類推，直至T中所有頂點都在同一連通分量上為止。例如圖為依照克魯斯卡爾演算法構造一棵最小生成樹的過程。代價分別為1，2，3，4的四條邊由於滿足上述條件，則先後被加入到T中，代價為5的兩條邊（1，4）和（3，4）被捨去。因為它們依附的兩頂點在同一連通分量上，它們若加入T中，則會使T中產生迴路，而下一條代價（=5）最小的邊（2，3）聯結兩個連通分量，則可加入T。因此，構造成一棵最小生成樹。上述演算法至多對 e條邊各掃描一次，假若以「堆」來存放網中的邊，則每次選擇最小代價的邊僅需O（loge）的時間（第一次需O（e））。又生成樹T的每個連通分量可看成是一個等價類，則構造T加入新的過程類似於求等價類的過程，由此可以以「樹與等價類」中介紹的 mfsettp類型來描述T，使構造T的過程僅需用O（eloge）的時間，由此，克魯斯卡爾演算法的時間復雜度為O（eloge）。^[1]

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

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

kruskal演算法：

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

⑩ 如何實現克魯斯卡爾演算法

最好結合具體題目實現，我這里有個題目，裡面有完整的代碼，慢慢理解就是了 http://blog.csdn.net/aihahaheihei/article/details/6751786
裡面還有很多，感興趣也可以看看