kruskal演算法的證明

⑴ kruskal演算法是什麼呢

kruskal演算法是求加權連通圖的最小生成樹的演算法。

kruskal演算法總共選擇n- 1條邊，(共n個點)所使用的貪心准則是:從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。

kruskal演算法分e步，其中e是網路中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。

Kruskal演算法基本思想：

每次選不屬於同一連通分量(保證不生成圈)且邊權值最小的頂點，將邊加入MST，並將所在的2個連通分量合並，直到只剩一個連通分量。

排序使用Quicksort(O(eloge))。

檢查是否在同一連通分量用Union-Find，每次Find和union運算近似常數。

Union-Find使用rank啟發式合並和路徑壓縮。

總復雜度O(eloge)=O(elogv) (因為e<n(n-1)/2)。

⑵ kruskal演算法是什麼

克魯斯卡爾演算法。

克魯斯卡爾演算法是求連通網的最小生成樹的另一種方法。與普里姆演算法不同，它的時間復雜度為O（eloge）（e為網中的邊數），所以，適合於求邊稀疏的網的最小生成樹。

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

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

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

⑶ 如何證明用 Kruskal's 演算法生成的樹是最小生成樹

為了避免最小生成樹不唯一的問題，可以不妨假設這個圖所有的邊長都不相等
（注意最小生成樹的總長度是原圖邊長的連續函數，所以可以這樣加強條件）

然後用反證法，假定Kruskal演算法中的第k步首次出現錯誤，演算法選了E1，但實際上必須選另一條邊E2才能得到最小生成樹T0
E1連接了兩個連通分支，這兩個連通分支在最終的T0里是連通的，所以把T0和E1放在一起之後形成的圖有一個環，在這個環里一定有k步或之後新選的邊（如果沒有的話僅憑前k-1條邊和E1不會構成環），依照E1的定義，這個環里存在比E1長的邊，用E1換掉這條邊之後得到的樹T1比T0更短，矛盾

⑷ 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

⑸ kruskal演算法

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

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

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

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

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

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

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

(6)kruskal演算法的證明擴展閱讀：

克魯斯卡爾演算法證明

假設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演算法的舉例描述

克魯斯卡爾演算法(Kruskal's algorithm)是兩個經典的最小生成樹演算法的較為簡單理解的一個。這裡面充分體現了貪心演算法的精髓。大致的流程可以用一個圖來表示。這里的圖的選擇借用了Wikipedia上的那個。非常清晰且直觀。
首先第一步，我們有一張圖，有若干點和邊
第一步我們要做的事情就是將所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這里再次體現了貪心演算法的思想。資源排序，對局部最優的資源進行選擇。
排序完成後，我們率先選擇了邊AD。這樣我們的圖就變成了
.
.
.
.
.
.
第二步，在剩下的邊中尋找。我們找到了CE。這里邊的權重也是5
.
.
.
.
.
.
依次類推我們找到了6,7,7。完成之後，圖變成了這個樣子。
.
.
.
.
.
.
下一步就是關鍵了。下面選擇那條邊呢？ BC或者EF嗎？都不是，盡管現在長度為8的邊是最小的未選擇的邊。但是他們已經連通了（對於BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以我們不需要選擇他們。類似的BD也已經連通了（這里上圖的連通線用紅色表示了）。
最後就剩下EG和FG了。當然我們選擇了EG。最後成功的圖就是下圖：
.
.
.
.
.
.
到這里所有的邊點都已經連通了，一個最小生成樹構建完成。
Kruskal演算法的時間復雜度由排序演算法決定，若採用快排則時間復雜度為O(N log N)。

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

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

kruskal演算法：

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

⑼ Kruskal 證明

離散書上應該都有 就是避圈法