背景：在學習圖的知識時，最小生成樹是一個最普遍的概念。它在日常生活中的應用很普遍，比如：有A、B、C、D、E五個城市，現在想在五個城市之間建設通信線路連通，每兩個城市之間修建線路的費用不同，我們當然想用最小的代價将五個城市通信連接配接起來，這時，如何擷取最小代價的方案，也就是如何找到最小生成樹就顯得尤為重要。
如何尋找最小生成樹，目前常用的有Prim(普裡姆)算法和Kruskal(克魯斯卡爾)算法，接下來我們一個一個詳細地介紹其原理。
為了友善了解，我們用一個圖來直覺地展示着兩個算法。下圖中A、B、C、D、E分别表示五個城市，每條邊上的數字表示兩個城市之間的修建通信線路的代價。設原圖中頂點集合為U，關系集合為V；生成樹中點的集合為u，關系集合為v。
Prim算法：
先選取一個頂點如A作為起點，将該點加入到集合u中，之後從和u中所有點相關聯，且終點在集合U-u中的所有邊中找出一條權值最小的邊。将該邊存入v中，同時将該邊的終點存入到u。重複以上步驟直至u中包含U中所有點。圖解如下所示。
下面我們再用文字來記錄一下Prim算法尋找最小生成樹的步驟：
選出頂點A，将A存入到集合u中。
此時u中隻有頂點A，和A相關聯且終點在U-u中的邊有A->B，A->C，A->E，這三條邊中權值最小的為A->B，将關系A->B加入到集合v，同時将點B加入到集合u。
此時u中有頂點A，B，和u中點相關聯且終點在U-u中的邊有A->C，A->E，B->C，這三條邊中權值最小的為A->C，将關系->C加入到集合v，同時将點C加入到集合u。
重複以上步驟，直至u中包含所有點。
Prim算法的實作代碼：
/**
* Prim算法代碼實作，預設圖中的第一個頂點序号為1
* @param graph 用于存儲頂點到頂點之間的權值，例如graph[1][3]表示頂點1到頂點3之間的權值
* @param n 用于表示頂點的數量
*/
void Prim(int graph[][MAX], int n){
int mincost[MAX];//數組存儲以i為頂點的邊的最小權值
for (int k = 0; k < MAX; ++k) {
mincost[k] = MAXCOST;
}
int start[MAX];//數組存儲以以i為頂點的最小權值的邊的起點
for (int j = 0; j < MAX; ++j) {
start[j] = 1;
}
int min = MAXCOST, min_index = 1;//min用于表示權值最小邊的權值，min_index用于表示該邊的終點
//初始化,預設所有頂點的權值最小邊是以第一個頂點為起點的
for (int i = 2; i <= n; ++i)
{
mincost[i] = graph[1][i];
}
//當mincost[i]=0時，表示将第i個頂點加入到到生成樹中
mincost[1] = 0;
//每次尋找最小權值的邊，将該邊的終點加入到最小生成樹中，循環n-1次，生成最小生成樹
for (int i = 2; i <= n; ++i)
{
min = MAXCOST;
//for循環周遊mincost數組，找到權值最小的邊
for (int i = 2; i <= n; ++i)
{
if (min > mincost[i] && mincost[i] != 0)
{
min = mincost[i];
min_index = i;
}
}
//将找到的最小邊的終點加入到生成樹中
mincost[min_index] = 0;
//更新mincost數組
for (int i = 2; i <= n; ++i)
{
if (graph[min_index][i] < mincost[i])
{
mincost[i] = graph[min_index][i];
start[i] = min_index;
}
}
}
//輸出最小生成樹
for (int i = 2; i <= n; ++i)
{
if (mincost[i] == 0)
{
cout<<start[i]<<"->"<<i<<"，權值為："<<graph[start[i]][i]<<endl;
}
}
}
/**
*測試用例
*/
int main() {
int graph[][6] = {
MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST,
MAXCOST, MAXCOST, 2, 5, MAXCOST, 9,
MAXCOST, 2, MAXCOST, 7, MAXCOST, MAXCOST,
MAXCOST, 5, 7, MAXCOST, 6, 4,
MAXCOST, MAXCOST, 6, MAXCOST, 11,
MAXCOST, 9, MAXCOST, 4, 11, MAXCOST,
};
Prim(graph, 5);
return 0;
}
Kruskal算法：
每次從集合V中選出一條權值最小，且加入到v中後不會形成環的邊，将該邊從V中删除，并加入到v中，同時将該邊的起點和終點加入到u中，若u中已有該頂點則忽略。重複上述步驟直至u中含有所有的點。圖解如下所示：
下面我們用文字來記錄一下Kruskal尋找最小生成樹的步驟：
從集合V中選出一條權值最小且加入到v中後不會形成環的邊，該邊為A->B，将該邊加入到v中，并從V中删除，同時将A，B兩個點加入到u中。
從集合V 中再選出一條權值最小且加入到v中後不會形成環的邊，該邊為C->E，将該邊加入到v中，并從V中删除，同時将C，E兩個點加入到u中。
從集合V 中再選出一條權值最小且加入到v中後不會形成環的邊，該邊為A->C，将該邊加入到v中，并從V中删除，同時将A，C兩個點加入到u中。由于A，C已經在u中，忽略這兩點。
從集合V 中再選出一條權值最小且加入到v中後不會形成環的邊，該邊為C->D，将該邊加入到v中，并從V中删除，同時将C，D兩個點加入到u中。由于C已經在u中，忽略C點。此時u中已經包含有所有的點，算法結束。
Kruskal實作代碼：
/**
* Kruskal代碼實作
* @param edges 存儲圖中的所有邊的集合
* @param n 集合edges的元素個數
*/
void Kruskal(list<Edge*> edges){
//初始化并查集資料結構
DSU *dsu = new DSU();
//将集合中的邊按照權值從小到大的順序排序
edges.sort(EdgeSort);
//每次從集合中拿出一個權值最小邊，如果起點和終點不在同一個連通圖内，則将該邊加入到最小生成樹中
for (int i = 0; i < edges.size(); ++i) {
Edge *edge = edges.front();
int from = edge->start;
int end = edge->end;
if (dsu->merge(from, end)){
cout<<from<<"->"<<end<<"，權值為："<<edge->weight<<endl;
}
edges.pop_front();
}
}
/**
* 并查集實作
*/
DSU::DSU() {
for (int i = 0; i < 10; ++i) {
father[i] = i;
}
}
/**
* 将兩個節點所在的連通子圖合并
* @param x
* @param y
* @return 布爾值，true表示起點和終點不在同一個連通圖内
*/
bool DSU::merge(int x, int y) {
int f1 = find(x);
int f2 = find(y);
//當x，y處于同一個連通圖中的時候，合并失敗
if (f1 == f2) {
return false;
}
father[f1] = f2;
return true;
}
/**
* 找到x的父節點
* @param x 參數節點
* @return 傳回父親節點
*/
int DSU::find(int x) {
if (x == father[x]){
return x;
}
return find(father[x]);
}
/**
*測試用例
*/
int main() {
Edge *edge1 = new Edge();
edge1->start = 1;
edge1->end = 2;
edge1->weight = 2;
Edge *edge2 = new Edge();
edge2->start = 1;
edge2->end = 3;
edge2->weight = 5;
Edge *edge3 = new Edge();
edge3->start = 1;
edge3->end = 5;
edge3->weight = 9;
Edge *edge4 = new Edge();
edge4->start = 2;
edge4->end = 3;
edge4->weight = 7;
Edge *edge5 = new Edge();
edge5->start = 3;
edge5->end = 4;
edge5->weight = 6;
Edge *edge6 = new Edge();
edge6->start = 3;
edge6->end = 5;
edge6->weight = 4;
Edge *edge7 = new Edge();
edge7->start = 4;
edge7->end = 5;
edge7->weight = 11;
list<Edge*> edges;
edges.push_back(edge1);
edges.push_back(edge2);
edges.push_back(edge3);
edges.push_back(edge4);
edges.push_back(edge5);
edges.push_back(edge6);
edges.push_back(edge7);
Kruskal(edges);
return 0;
}