1. 并查集
看《大話資料結構》中的克魯斯卡爾算法時一直沒能真正了解代碼含義，關鍵是因為沒搞懂并查集，直到看了這篇文章。
并查集是一種樹型的資料結構，用于處理一些不相交集合的合并及查詢問題。對于圖中的兩個頂點A和B，通過并查集可以判斷是否AB之間是否有路徑。同時，也可以判斷将A和B相連之後是否可以形成環，因為如果AB之間有路徑的話，那麼再将A和B相連就會出現環。
并查集的基本操作包括：初始化，查找，合并。為了提高查找的效率通常會用到路徑壓縮。
我們使用數組
int parent[maxSize]
來存儲每個頂點的爸爸（不太嚴謹，暫時這樣叫吧），
parent[i]
存儲的就是頂點
i
的爸爸，如果頂點
i
與頂點
j
的爸爸相同，說明他們在一個集合中，那麼他們可以連通。
1.1初始化
初始化時可以将每個頂點的爸爸初始化為他自己，自己是自己的爸爸（。。。）
for(int i = 0; i < N; i++)
parent[i] = i;
1.2查找
找爸爸，這裡找的是爸爸的爸爸的爸爸的。。。直到找到自己是自己爸爸的那個頂點。
int Find(int v) {
while(parent[v] != v) {
v = parent[v];
}
return v;
}
1.3合并
如果兩個頂點沒有共同的爸爸，即他們不在同一個樹中，則将兩者合并到一個樹中。
void Union(int s, int e) {
int sRoot = Find(s);
int eRoot = Find(e);
if(sRoot != eRoot) {
parent[sRoot] = eRoot;//s和e的祖宗不同,将兩個樹合成一個樹,這裡假設s的祖宗是e的祖宗的兒砸
}
}
s和e的祖宗不同,将兩個樹合成一個樹,這裡假設s的祖宗是e的祖宗的兒砸，這個假設不一定合适，憑什麼s的祖宗輩分低，畢竟現在誰都想當爸爸（手動狗頭）。
合并的時候誰當爸爸也是有講究的，具體1.4路徑壓縮。
1.4路徑壓縮
引用這篇部落格的例子：
路徑壓縮是為了友善找到爸爸（老大）。
int Find(int v) {
int root = v;
while(parent[root] != root) {
root = parent[root];//尋找祖先結點
}
//将沿途的非祖先結點的爸爸全部變為祖先結點（現在root為祖先結點）
int tmp;
while(v != root) {
tmp = parent[v];//儲存v的爸爸
parent[v] = root;//将v的爸爸改為最祖先的結點
v = tmp;//對v的爸爸進行同樣的操作
}
return v;
}
我們也可以用遞歸的思路重寫上面的代碼：
int Find(int v) {
if(v != parent[v]) {
parent[v] = Find(parent[v]);
}
return parent[v];
}
路徑壓縮後樹的深度明顯減少了，利于查找，當我們合并兩個樹時，選擇層數多的樹當爸爸會讓整個樹的深度更小。那麼我們在合并操作時，最好讓深度比較深的當爸爸。
我們定義一個數組存放每個結點的深度（或者稱為rank），初始化為1，即每個結點隻包含自己。
int rank[maxSize]
.
for(int i = 0; i < N; i++)
rank[i] = 1;
重新定義合并函數：
bool Union(int s, int e){
int sRoot = Find(s);
int eRoot = Find(e);
if(sRoot != eRoot){
if(rank[sRoot] < rank[eRoot]){//sRoot是小樹,将其加入大樹中
parent[sRoot] = eRoot;
rank[eRoot] += rank[sRoot];
}else{//eRoot為小樹,将其加入sRoot中
parent[eRoot] = sRoot;
rank[sRoot] += rank[eRoot];
}
return true;//s和e爸爸不同,需要合并傳回true
}
return false;//s和e爸爸相同,不需要合并,傳回false
}
2. 克魯斯卡爾算法
克魯斯卡爾算法的原理在此不再解釋，貪心算法的典型應用。
以下面這個圖為例：
上代碼：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/******圖的鄰接矩陣存儲結構*******/
typedef int VertexType; //頂點類型, 使用者自定義
typedef int EdgeType; //權值類型, 使用者自定義
#define MAXVEX 9 //最大頂點個數
#define INFINITY INT_MAX
vector<int> parent(MAXVEX);
vector<int> Rank(MAXVEX);
typedef struct
{
vector<VertexType> vexs; //頂點矩陣
vector<vector<EdgeType>> arc;//鄰接矩陣, 二維矩陣
int numVertexs, numEdges; //圖中的頂點數和邊數
}MGraph;
struct Edge {
int begin;//這裡是無向圖,起始節點預設為下标較小的點
int end;
int weight;
bool operator < (const Edge& a) const {
return weight < a.weight;
}
};//邊集數組
int Find(int v) {
if (v != parent[v])
parent[v] = Find(parent[v]);
return parent[v];
}
bool Union(int s, int e) {
int sRoot = Find(s);
int eRoot = Find(e);
if (sRoot != eRoot) {
if (Rank[sRoot] < Rank[eRoot]) {//sRoot是小樹,将其加入大樹中
parent[sRoot] = eRoot;
Rank[eRoot] += Rank[sRoot];
}
else {//eRoot為小樹,将其加入sRoot中
parent[eRoot] = sRoot;
Rank[sRoot] += Rank[eRoot];
}
return true;//s和e爸爸不同,需要合并傳回true
}
return false;//s和e爸爸相同,不需要合并,傳回false
}
//最小生成樹克魯斯卡爾算法
void MinSpanTree_Kruskal(MGraph G) {
vector<Edge> edges(G.numEdges);//邊集數組
//根據G的鄰接矩陣表示得到邊集數組
int k = 0;
for (int i = 0; i < G.numVertexs; i++) {
for (int j = i + 1; j < G.numVertexs; j++) {//無向圖的鄰接矩陣是對稱的,不需要将重複的邊添加到邊集數組中
if (G.arc[i][j] != INT_MAX) {
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
k++;
}
}
}
//對邊集數組進行排序
sort(edges.begin(), edges.end());
//初始化并查集與Rank
for (int i = 0; i < G.numVertexs; i++) {
parent[i] = i;//初始化數組值
Rank[i] = 1;
}
for (int i = 0; i < G.numEdges; i++) {
if (Union(edges[i].begin, edges[i].end)) {
cout << "(" << edges[i].begin << ", " << edges[i].end << ")\t" << edges[i].weight << endl;
}
}
}
int main()
{
MGraph G;
G.numVertexs = 9;//9個頂點
G.numEdges = 15;//15條邊
for (int i = 0; i < G.numVertexs; i++)
G.vexs.push_back(i);
//鄰接矩陣
G.arc = {
{ 0, 10, INFINITY, INFINITY, INFINITY, 11, INFINITY, INFINITY, INFINITY },
{ 10, 0, 18, INFINITY, INFINITY, INFINITY, 16, INFINITY, 12 },
{ INFINITY, 18, 0, 22, INFINITY, INFINITY, INFINITY, INFINITY, 8 },
{ INFINITY, INFINITY, 22, 0, 20, INFINITY, 24, 16, 21 },
{ INFINITY, INFINITY, INFINITY, 20, 0, 26, INFINITY, 7, INFINITY },
{ 11, INFINITY, INFINITY, INFINITY, 20, 0, 17, INFINITY, INFINITY },
{ INFINITY, 16, INFINITY, INFINITY, INFINITY, 17, 0, 19, INFINITY },
{ INFINITY, INFINITY, INFINITY, 16, 7, INFINITY, 19, 0, INFINITY },
{ INFINITY, 12, 8, 21, INFINITY, INFINITY, INFINITY, INFINITY, 0 }
};
MinSpanTree_Kruskal(G);
system("pause");
return 0;
}
在搞清楚并查集之後，再看克魯斯卡爾算法的實作就比較簡單了。
最核心的部分就是這段：
for (int i = 0; i < G.numEdges; i++) {
if (Union(edges[i].begin, edges[i].end)) {
cout << "(" << edges[i].begin << ", " << edges[i].end << ")\t" << edges[i].weight << endl;
}
}
邊排序結果：
運作結果：