最小生成樹

1.什么是圖的最小生成樹（MST）?

用N-1條邊連接N個點，形成的圖形一定是樹。
一個具有N個點的有權無向圖，最小生成樹就是從圖的所有邊中選擇N-1條出來，連接所有的N個點。這個N-1條邊的邊權之和是所有方案中最小的。

2.最小生成樹用來解決什么問題？

用來解決如何用最小的“代價”用N-1條邊連接N個點的問題。

Kruskal（克魯斯卡爾）算法

Kruskal算法是一種巧妙利用并查集來求最小生成樹的算法。
Kruskal首先初始化并查集，把N個點看做N個獨立的集合。再將所有的邊從小到大排序。然后按順序枚舉每一條邊，如果這條邊連接的兩個點屬于兩個集合，那么就把這條邊加入最小生成樹，并且合并這兩個集合；如果這條邊連接的兩個點屬于同一集合，就跳過。直到選取了N-1條邊為止。

算法描述

1.初始化計數器k=0；MST=0；（K用來記錄邊數，MST用來記錄邊的權值之和）
2.初始化并查集：Parent[x]=x;（把n個點初始化為n個獨立的集合，每個點的父節點是它自身）
3.將所有邊用Sort()從小到大排序

 for(i=1;i<=M;i++){ // M為邊數，對邊進行從小到大的循環if(Find(E[i].u)!=Find(E[i].v)){ // 調用查找函數,第i條邊的端點u,第i條邊的端點v，即查詢端點u和端點v的根節點，如果根節點不相等，說明兩個點處于兩個不相同的集合之中Union(E[i].u,E[i].v);//把u，v個治所在的集合合并  // E[i]進行邊集數組儲存，表示第i條邊MST+=E[i].w; //把每條邊的邊權相加k++; //計數器 }if(K==N-1) break; //說明生成最小生成樹} 

圖解

//最小生成樹：Kruskal算法+邊集存儲+并查集#include<iostream>
#include<algorithm>
using namespace std;struct Edge{int u,v,w;
}E[101]; //邊集數組儲存 
int Parent[101];//并查集,定義Parent[]數組 int Find(int x) //查找根節點并壓縮路徑
{if(Parent[x]!=x)Parent[x]=Find(Parent[x]);return Parent[x]; } void Union(int x,int y){ //合并兩個集合 Parent[Find(y)]=Find(x);}int Cmp(const Edge &a,const Edge &b){ //自定義比較函數 return (a.w<b.w)?1:0; }int main(){int i,j,k=0,MST=0;int N=5,M=7;//頂點數和邊數 int e[9][3]={{1,2,2},{1,3,5},{1,4,2},{2,3,3},{3,4,1},{2,5,4},{3,5,6}};for(i=1;i<=M;i++){E[i].u=e[i-1][0];E[i].v=e[i-1][1];E[i].w=e[i-1][2];}//存邊for(i=1;i<=M;i++){Parent[i]=i; //初始化并查集} sort(E+1,E+M+1,Cmp);//調用快排序,對應的時間復雜度為O(E*logE) printf("u v w\n");for(i=1;i<=M;i++){printf("%d %d %d\n",E[i].u,E[i].v,E[i].w);//跟蹤 } //求解最小生成樹 printf("\n u v w MST\n");   //時間復雜度為O(M)或者O(E) for(i=1;i<=M;i++){if(Find(E[i].u)!=Find(E[i].v)){Union(E[i].u,E[i].v);MST+=E[i].w;k++;printf("%d %d %d %d\n",E[i].u,E[i].v,E[i].w,MST);//跟蹤}if(k==N-1) {break;} }printf("\n MST=%d\n",MST);}