樹（Tree）：如果一個無向連通圖中不存在回路，則這種圖稱為樹。
生成樹 （Spanning Tree）：無向連通圖G的一個子圖如果是一顆包含G的所有頂點的樹，則該子圖稱為G的生成樹。
生成樹是連通圖的極小連通子圖。這裡所謂極小是指：若在樹中任意增加一條邊，則将出現一條回路；若去掉一條邊，将會使之變成非連通圖。
最小生成樹（Minimum Spanning Tree，MST）：或者稱為最小代價樹Minimum-cost Spanning Tree:對無向連通圖的生成樹，各邊的權值總和稱為生成樹的權，權最小的生成樹稱為最小生成樹。
構成生成樹的準則有三條：
<1> 必須隻使用該網絡中的邊來構造最小生成樹。
<2> 必須使用且僅使用n-1條邊來連接配接網絡中的n個頂點
<3> 不能使用産生回路的邊。
構造最小生成樹的算法主要有：克魯斯卡爾（Kruskal）算法和普利姆（Prim）算法他們都遵循以上準則。
接下分别讨論一下這兩種算法以及判定最小生成樹是否唯一的方法。
克魯斯卡爾算法的基本思想是以邊為主導地位，始終選擇目前可用（所選的邊不能構成回路）的最小權植邊。是以Kruskal算法的第一步是給所有的邊按照從小到大的順序排序。這一步可以直接使用庫函數qsort或者sort。接下來從小到大依次考察每一條邊（u，v）。
具體實作過程如下：
<1> 設一個有n個頂點的連通網絡為G（V,E），最初先構造一個隻有n個頂點，沒有邊的非連通圖T={V,空}，圖中每個頂點自成一格連通分量。
<2> 在Ｅ中選擇一條具有最小權植的邊時，若該邊的兩個頂點落在不同的連通分量上，則将此邊加入到Ｔ中；否則，即這條邊的兩個頂點落到同一連通分量 上，則将此邊舍去（此後永不選用這條邊），重新選擇一條權植最小的邊。
<3> 如此重複下去，直到所有頂點在同一連通分量上為止。
下面是僞代碼：
// 把所有邊排序，記第i小的邊為e[i] (1<=i<=m)m為邊的個數
// 初始化MST為空
// 初始化連通分量，使每個點各自成為一個獨立的連通分量
for (int i = 0; i < m; i++)
{
if (e[i].u和e[i].v不在同一連通分量)
{
// 把邊e[i]加入ＭＳＴ
// 合并e[i].u和e[i].v所在的連通分量
}
}
上面的僞代碼，最關鍵的地方在于“連通分量的查詢和合并”，需要知道任意兩個點是否在同一連通分量中，還需要合并兩個連通分量。
這個問題正好可以用并查集完美的解決（不得不佩服前輩們聰明才智啊！）
并查集（Union-Find set）這個資料結構可以友善快速的解決這個問題。基本的處理思想是：初始時把每個對象看作是一個單元素集合；然後依次按順序讀入聯通邊，将連通邊中的兩個元素合并。在此過程中将重複使用一個搜尋（Find）運算，确定一個集合在那個集合中。當讀入一個連通邊（ｕ，ｖ）時，先判斷ｕ和ｖ是否在同一個集合中，如果是則不用合并；如果不是，則用一個合并（Union）運算把ｕ、ｖ所在集合合并，使得這兩個集合中的任意兩個元素都連通。是以并查集在處理時，主要用到搜尋和合并兩個運算。
為了友善并查集的描述與實作，通常把先後加入到一個集合中的元素表示成一個樹結構，并用根結點的序号來表示這個集合。是以定義一個parent[n]的數組，parent[i]中存放的就是結點ｉ所在的樹中結點ｉ的父親節點的序号。例如，如果parent[4]=5，就是說４号結點的父親結點是５号結點。約定：如果ｉ的父結點（即parent[i]）是負數，則表示結點ｉ就是它所在的集合的根結點，因為集合中沒有結點的序号是負的；并且用負數的絕對值作為這個集合中所含結點的個數。例如，如果parent[7]=-4，說明７号結點就是它所在集合的根結點，這個集合有四個元素。初始時結點的parent值為－１（每個結點都是根結點，隻包含它自己一個元素）。
實作Kruskal算法資料結構主要有3個函數。
void UFset() // 初始化
{
for (int i = 0; i < n; i ++)
parent[i] = -1;
}
int Find(int x) // 查找并傳回結點x所屬集合的根結點
{
int s; // 查找位置
for (s = x; parent[s]>=0; s = parent[s]); // 注意這裡的 ;
while (s != x) // 優化方案 -- 壓縮路徑，使後續的查找
{
int tmp = parent[x];
parent[x] = s;
x = tmp;
}
return s;
}
// R1和R2是兩個元素，屬于兩個不同的集合，現在合并這兩個集合
void Union (int R1, int R2)
{
// r1位R1的根結點，r2位R2的根結點
int r1 = Find(R1), r2 = Find(R2);
int tmp = parent[r1] + parent[r2]; // 兩個集合的結點個數之和（負數）
// 如果R2所在樹結點個數 > R1所在樹結點個數
// 注意parent[r1]和parent[r2]都是負數
if(parent[r1] > parent[r2]) // 優化方案 -- 權重法則
{
parent[r1] = r2; // 将根結點r1所在的樹作為r2的子樹（合并）
parent[r2] = tmp; // 跟新根結點r2的parent[]值
}
else
{
parent[r2] = r1; // 将根結點r2所在的樹作為r1的子樹（合并）
parent[r1] = tmp; // 跟新根結點r1的parent[]值
}
}
接下來對 Find 函數和 Union 函數的實作過程作詳細解釋。
Find 函數：在 Find 函數中如果僅僅靠一個循環來直接得到結點所屬集合的根結點的話，通過多次的 Union 操作就會有很多結點在樹的比較深層次中，再查找起來就會很費時。可以通過壓縮路徑來加快後續的查找速度：增加一個 While 循環，每次都把從結點 x 到集合根結點的路徑上經過的結點直接設定為根結點的子女結點。雖然這增加了時間，但以後的查找會更快。如圖 3.4 所示，假設從結點 x = 6 開始壓縮路徑，則從結點 6 到根結點1 的路徑上有 3 個結點：6、10、8，壓縮後，這 3 個結點都直接成為根結點的子女結點，如圖(b)所示。
并查集：Find函數中的路徑壓縮
Union 函數：兩個集合并時，任一方可做為另一方的子孫。怎樣來處理呢，現在一般采用權重合并，把兩個集合中元素個數少的根結點做為元素個數多的根結點的子女結點。這樣處理有什麼優勢呢？直覺上看，可以減少樹中的深層元素的個數，減少後續查找時間。
例如，假設從 1 開始到 n，不斷合并第 i 個結點與第 i+1 個結點，采用權重合并思路的過程如下圖所示（各子樹根結點上方的數字為其 parent[ ]值）。這樣查找任一結點所屬集合的時間複雜度幾乎都是 O(1)！！！
并查集：權重合并
不用權重規則可能會得到下圖所示的結果。這就是典型的退化樹（隻有一個葉結點，且每個非葉結點隻有一個子結點）現象，再查找起來就會很費時，例如查找結點 n 的根結點時複雜度為 O(n)。
并查集：合并時不權重的結果。
例 利用 Kruskal 算法求無向網的最小生成樹，并輸出依次選擇的各條邊及最終求得的最小生成樹的權。
假設資料輸入時采用如下的格式進行輸入：首先輸入頂點個數 n 和邊數 m，然後輸入 m 條邊的資料。每條邊的資料格式為：u v w，分别表示這條邊的兩個頂點及邊上的權值。頂點序号從 1開始計起。
分析：
在下面的代碼中，首先讀入邊的資訊，存放到數組 edges[ ]中，并按權值從小到大進行排序。
Kruskal( )函數用于實作 ：首先初始化并查集，然後從 edges[ ]數組中依次選用每條邊，如果這條邊的兩個頂點位于同一個連通分量，則要棄用這條邊；否則合并這兩個頂點所在的連通分量。
代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXN 11 //頂點個數的最大值
#define MAXM 20 //邊的個數的最大值
using namespace std;
struct edge //邊
{
int u, v, w; //邊的頂點、權值
}edges[MAXM]; //邊的數組
int parent[MAXN]; //parent[i]為頂點 i 所在集合對應的樹中的根結點
int n, m; //頂點個數、邊的個數
int i, j; //循環變量
void UFset( ) //初始化
{
for( i=1; i<=n; i++ )
parent[i] = -1;
}
int Find( int x ) //查找并傳回節點 x 所屬集合的根結點
{
int s; //查找位置
for( s=x; parent[s]>=0; s=parent[s] );
while( s!=x ) //優化方案―壓縮路徑，使後續的查找操作加速。
{
int tmp = parent[x];
parent[x] = s;
x = tmp;
}
return s;
}
//将兩個不同集合的元素進行合并，使兩個集合中任兩個元素都連通
void Union( int R1, int R2 )
{
int r1 = Find(R1), r2 = Find(R2); //r1 為 R1 的根結點，r2 為 R2 的根結點
int tmp = parent[r1] + parent[r2]; //兩個集合結點個數之和(負數)
//如果 R2 所在樹結點個數 > R1 所在樹結點個數(注意 parent[r1]是負數)
if( parent[r1] > parent[r2] ) //優化方案――權重法則
{
parent[r1] = r2;
parent[r2] = tmp;
}
else
{
parent[r2] = r1;
parent[r1] = tmp;
}
}
bool cmp( edge a, edge b ) //實作從小到大排序的比較函數
{
return a.w <= b.w;
}
void Kruskal( )
{
int sumweight = 0; //生成樹的權值
int num = 0; //已選用的邊的數目
int u, v; //選用邊的兩個頂點
UFset( ); //初始化 parent[]數組
for( i=0; i<m; i++ )
{
u = edges[i].u; v = edges[i].v;
if( Find(u) != Find(v) )
{
printf( "%d %d %d\n", u, v, edges[i].w );
sumweight += edges[i].w; num++;
Union( u, v );
}
if( num>=n-1 ) break;
}
printf( "weight of MST is %d\n", sumweight );
}
int main( )
{
int u, v, w; //邊的起點和終點及權值
scanf( "%d%d", &n, &m ); //讀入頂點個數 n
for( int i=0; i<m; i++ )
{
scanf( "%d%d%d", &u, &v, &w ); //讀入邊的起點和終點
edges[i].u = u; edges[i].v = v; edges[i].w = w;
}
sort(edges,edges+m,cmp);
Kruskal();
return 0;
}
// 把邊e[i]加入ＭＳＴ
10 // 合并e[i].u和e[i].v所在的連通分量
11 }
12 } 上面的僞代碼，最關鍵的地方在于“連通分量的查詢和合并”