當前位置:首頁 » 操作系統 » 克魯斯卡爾演算法

克魯斯卡爾演算法

發布時間: 2022-01-14 00:43:26

⑴ 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的。
而判斷循環是如果兩個的最終的開始節點是同一個,就說明你加上這條邊就形成循環了,這條邊就不能加

⑶ 克魯斯卡爾演算法的演算法描述

克魯斯卡爾演算法的時間復雜度為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)。

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

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

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

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

(4)克魯斯卡爾演算法擴展閱讀:

克魯斯卡爾演算法證明

假設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)。

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

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

⑹ kruskal演算法

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

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

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

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

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

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

看這段代碼真令我頭疼,我就告訴你思路吧!
並查集你會不會?如果會的話那就好辦。
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,則說明此圖為非連通圖

熱點內容
javanio教程 發布:2024-04-13 19:45:24 瀏覽:667
如何設置伺服器ftp 發布:2024-04-13 19:45:21 瀏覽:30
python搭建web 發布:2024-04-13 19:34:42 瀏覽:738
中等伺服器是什麼 發布:2024-04-13 19:33:55 瀏覽:91
c語言查體 發布:2024-04-13 19:22:46 瀏覽:330
伺服器600g硬碟是什麼意思 發布:2024-04-13 19:20:59 瀏覽:95
三國殺對對碰通關腳本 發布:2024-04-13 18:52:01 瀏覽:570
php函數被調用函數 發布:2024-04-13 18:08:31 瀏覽:975
圖片的二級緩存 發布:2024-04-13 17:55:33 瀏覽:338
什麼是陰陽師配置要求 發布:2024-04-13 17:55:32 瀏覽:808