克魯斯卡爾算法

Kruskal算法是一種用來查找最小生成樹的算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim算法和Boruvka算法等。三種算法都是貪心算法的套用。和Boruvka算法不同的地方是，Kruskal算法在圖中存在相同權值的邊時也有效。

基本介紹

• 中文名：克魯斯卡爾算法
• 外文名：Kruskal algorithm
• 套用領域：運籌學
• 時間複雜度：O(|E|log|E|)

基本思想

先構造一個只含 n 個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。

步驟

1. 新建圖G，G中擁有原圖中相同的節點，但沒有邊；
   
2. 將原圖中所有的邊按權值從小到大排序；
   
3. 從權值最小的邊開始，如果這條邊連線的兩個節點於圖G中不在同一個連通分量中，則添加這條邊到圖G中；
   
4. 重複3，直至圖G中所有的節點都在同一個連通分量中。
   

證明

1. 這樣的步驟保證了選取的每條邊都是橋，因此圖G構成一個樹。
   
2. 為什麼這一定是最小生成樹呢？關鍵還是步驟3中對邊的選取。算法中總共選取了n-1條邊，每條邊在選取的當時，都是連線兩個不同的連通分量的權值最小的邊
   
3. 要證明這條邊一定屬於最小生成樹，可以用反證法：如果這條邊不在最小生成樹中，它連線的兩個連通分量最終還是要連起來的，通過其他的連法，那么另一種連法與這條邊一定構成了環，而環中一定有一條權值大於這條邊的邊，用這條邊將其替換掉，圖仍舊保持連通，但總權值減小了。也就是說，如果不選取這條邊，最後構成的生成樹的總權值一定不會是最小的。
   

時間複雜度

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

C語言程式

#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;const int M = 1e5+7;struct node{  int a,b,val;} Q[M];int fa[M];int Rd(){  int res=0;char c;  while(c=getchar(),!isdigit(c));  do {    res=(res<<3)+(res<<1)+(c^48);  } while(c=getchar(),isdigit(c));  return res;}bool cmp(LZ a,LZ b){  return a.val<b.val;}int getfa(int v){    if(fa[v]!=v)fa[v]=getfa(fa[v]);    return fa[v];}int main(){    int i,j,n,m,x,y;    scanf("%d%d",&n,&m);    for(i=1;i<=m;i++)    {        Q[i].a=Rd();Q[i].b=Rd();Q[i].val=Rd();    }    sort(Q+1,Q+m+1,cmp);    for(i=1;i<=n;i++)    {        fa[i]=i;    }    int sum=0,cut=0;    for(i=1;i<=m;i++)    {        x=getfa(Q[i].a);        y=getfa(Q[i].b);                if(x==y)continue;                sum+=Q[i].val;                if(++cut==n-1)break;                fa[x]=y;        }        printf("%d",sum);        return 0;}