C++算法之克魯斯卡爾算法
克魯斯卡爾算法是計算最小生成樹的一種算法。和prim算法（上，中，下）按照節點進行查找的方法不一樣，克魯斯卡爾算法是按照具體的線段進行的。現在我 們假設一個圖有m個節點，n條邊。首先，我們需要把m個節點看成m個獨立的生成樹，并且把n條邊按照從小到大的數據進行排列。在n條邊中，我們依次取出其 中的每一條邊，如果發現邊的兩個節點分別位于兩棵樹上，那么把兩棵樹合并成為一顆樹；如果樹的兩個節點位于同一棵樹上，那么忽略這條邊，繼續運行。等到所 有的邊都遍歷結束之后，如果所有的生成樹可以合并成一條生成樹，那么它就是我們需要尋找的最小生成樹，反之則沒有最小生成樹。
上面的算法可能聽上去有些費解，我們可以用一個示例說明一下，
/*
- 9
- D -----------
- 3 | |
- | 6 |
- A ------- B
- | |
- | 7 | 5
- -------C---- **/
</pre>
現在有這么4個點。其中 A-D 為3， A-C為7，A-B為6，B-D為9，B-C為5，下面就開始計算，我們首先默認所有的點都是單獨的最小生成樹，
/*
- D
- A B
- C
*/
</pre>
第一步，按照從小到大的順序，我們加入最小的邊A-D，
/
- D
- 3 |
- |
- A B
- C
*/
</pre>
然后，我們發現下面最小的邊是B-C，
/
- D
- 3 |
- |
- A B
- |
- | 5
- C----
*/
</pre> 接著，我們發現最小的邊是A-B，因為點A和點B位于不同的最小生成樹上面，所以繼續合并，/
- D
- 3 |
- | 6
- A---------- B
- |
- | 5
- C---- **/
</pre>
接下來，我們還會遍歷A-C，B-D，但是我們發現此時邊的節點都已經遍歷過了，所以均忽略，最小生成樹的結構就是上面的內容。
那么最小生成樹的數據結構是什么，應該怎么定義，不知道朋友們還記得否？我們曾經在prim算法中討論過，
/ 直連邊 /
typedef struct _DIR_LINE
{
int start;
int end;
int weight;
struct _DIR_LINE* next;
}DIR_LINE;/ 最小生成樹 /
typedef struct _MINI_GENERATE_TREE
{
int node_num;
int line_num;
int pNode;
DIR_LINE pLine;
}MINI_GENERATE_TREE;/ 節點邊信息 /
typedef struct _LINE
{
int end;
int weight;
struct _LINE* next;
}LINE;/節點信息/
typedef struct _VECTEX
{
int start;
int number;
LINE neighbor;
struct _VECTEX next;
}VECTEX;/ 圖信息 /
typedef struct _GRAPH
{
int count;
VECTEX* head;
}GRAPH;</pre> 前面說到，克魯斯卡爾的算法是按照各個line的權重依次進行添加的，那么這就涉及到一個權重的排序問題。怎么排序呢？可以采用最簡單的冒泡排序算法。可是這里排序的是數據結構，怎么辦呢？那就只好采用通用排序算法了。
void bubble_sort(void array[], int length, int (compare)(void, void), void(*swap)(void, void))
{
int outer;
int inner;for(outer = length -1; outer >0; outer --){ for(inner = 0; inner < outer; inner ++){ if(compare(array[inner], array[inner + 1])) swap(&array[inner], &array[inner + 1]); } } return;}
</pre> 所以，這里就要添加上屬于DIR_LINE的compare和swap函數，
int compare(void data1, void data2)
{
DIR_LINE line1 = (DIR_LINE) data1;
DIR_LINE line2 = (DIR_LINE) data2;return (line1->weight > line2->weight) ? 1 : 0;}
void swap(void data1, void data2)
{
DIR_LINE* median;
DIR_LINE line1;
DIR_LINE line2;line1 = (DIR_LINE**) data1; line2 = (DIR_LINE**) data2; median = *line1; *line1 = *line2; *line2 = median;}
</pre> 排序結束之后，我們就開始線段的插入工作，那么進行線段插入的時候，我們需要知道當前線段是不是在某一個最小生成樹中已經存在了，如果是這樣的話，那么這個線段就要被忽略了。所以，這中間還存在一個判斷的問題，
int getVectexNumFromTree(MINI_GENERATE_TREE* pTree, int start, int end)
{
int index;
int total;total = 0; for(index = 0; index < pTree->node_num; index++){ if(start == pTree->pNode[index]){ total ++; continue; } if(end == pTree->pNode[index]){ total ++; } } return total;}
int isDoubleVectexExistInTree(MINI_GENERATE_TREE* pTree[], int length, int start, int end)
{
int index = 0;
int value = 0;
int number = 0;for(index = 0; index < length; index ++){ number = getVectexNumFromTree(pTree[index], start, end); if(number > value) value = number; } return (value == 2) ? 1 : 0;}
</pre> 線段的判斷之后，如果發現在兩顆獨立的最小生成樹上面，那么還需要進行合并操作，刪除其中一個最小生成樹，把另外一個生成樹的所有點和線段都要添加到沒有刪除的這顆最小生成樹上面。當然還有一點不要忘記了，最后還要加上端口分別在兩棵樹上的這個線段。
void mergeTwoMiniGenerateTree(MINI_GENERATE_TREE pTree[], int length, int start, int end, int weight)
{
MINI_GENERATE_TREE pFirst;
MINI_GENERATE_TREE pSec;
DIR_LINE line;
int index;/* 刪除多余的最小生成樹 */ pFirst = find_tree_by_index(pTree, length, start); pSec = find_tree_by_index(pTree, length, end); delete_mini_tree_from_group(pTree, length, pSec); /* 合并節點 */ for(index = 0; index < pSec->node_num; index ++){ pFirst->pNode[pFirst->node_num + index] = pSec->pNode[index]; } pFirst->node_num += pSec->node_num; /* 合并線段 */ for(line = pSec->pLine; line; line = line->next){ insert_line_into_queue(&pFirst->pLine, line->start, line->end, line->weight); } insert_line_into_queue(&pFirst->pLine, start, end, weight); /* 函數返回 */ return;}
</pre> 總結：
（1）這部分主要介紹了克魯斯卡爾算法編寫中需要處理的三個問題，排序、查找和合并
（2）復雜的函數都是由簡單的函數構造而成的，我們可以把算法分成幾個獨立的部分，各個擊破
（3）解決了這三個問題，下一篇博客就可以進行歸總分析處理，邏輯上也十分清晰了
前面在討論克魯斯卡爾的算法的時候，我們分析了算法的基本過程、基本數據結構和算法中需要解決的三個問題（排序、判斷、合并）。今天，我們繼續完成剩下部分的內容。合并函數中，我們調用了兩個基本函數，find_tree_by_index和delete_mini_tree_from_group，下面給出詳細的計算過程。MINI_GENERATE_TREE find_tree_by_index(MINI_GENERATE_TREE pTree[], int length, int point)
{
int outer;
int inner;for(outer = 0; outer < length; outer++){ for(inner = 0; inner < pTree[outer]->node_num; inner ++){ if(point == pTree[outer]->pNode[inner]) return pTree[outer]; } } return NULL;}
void delete_mini_tree_from_group(MINI_GENERATE_TREE pTree[], int length, MINI_GENERATE_TREE pIndex)
{
int index;for(index = 0; index < length; index ++){ if(pIndex == pTree[index]) break; } memmove(&pTree[index +1], &pTree[index], sizeof(MINI_GENERATE_TREE*) * (length -1 - index)); return;}
</pre> 下面就可以開始編寫克魯斯卡爾最小生成樹了，代碼如下所示，
MINI_GENERATE_TREE _kruskal(MINI_GENERATE_TREE pTree[], int length, DIR_LINE* pLine[], int number)
{
int index;if(NULL == pTree || NULL == pLine) return NULL; for(index = 0; index < number; index ++){ bubble_sort((void**)pLine, number, compare, swap); if(2 == isDoubleVectexExistInTree(pTree, length, pLine[index]->start, pLine[index]->end)) continue; mergeTwoMiniGenerateTree(pTree, length, pLine[index]->start, pLine[index]->end, pLine[index]->weight); length --; } return (1 != length) ? NULL : pTree[0];}
</pre> 要進行上面的計算，我們還需要算出頂點的個數，線段的個數，所以函數還需要進一步完善和補充，
MINI_GENERATE_TREE kruskal(GRAPH pGraph)
{
MINI_GENERATE_TREE pTree;
DIR_LINE pLine;
int count;
int number;if(NULL == pGraph) return NULL; count = pGraph->count; number = get_total_line_number(pGraph); pTree = get_tree_from_graph(pGraph); pLine = get_line_from_graph(pGraph); return _kruskal(pTree, count, pLine, number);}
</pre> 這樣，克魯斯卡爾算法大體上算結束了，其中get_total_line_number、get_tree_from_graph、get_line_from_graph函數都比較簡單，朋友們可以自己繼續完成，但是要好好測試。
總結：
（1）代碼中沒有考慮內存的釋放問題，需要改進和提高
（2）部分代碼可以復用prim算法中的內容，數據結構也一樣
（3）算法的編寫貴在理解，只要步驟對了，再加上測試，一般問題都不大