【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前面說到，克魯斯卡爾的算法是按照各個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;
}
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;
} 所以，這裡就要添加上屬於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;
}
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;
} 排序結束之後，我們就開始線段的插入工作，那麼進行線段插入的時候，我們需要知道當前線段是不是在某一個最小生成樹中已經存在了，如果是這樣的話，那麼這個線段就要被忽略了。所以，這中間還存在一個判斷的問題，
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;
}
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;
} 線段的判斷之後，如果發現在兩顆獨立的最小生成樹上面，那麼還需要進行合並操作，刪除其中一個最小生成樹，把另外一個生成樹的所有點和線段都要添加到沒有刪除的這顆最小生成樹上面。當然還有一點不要忘記了，最後還要加上端口分別在兩棵樹上的這個線段。
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(start);
pSec = find_tree_by_index(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;
}
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(start);
pSec = find_tree_by_index(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;
}
文章總結：
（1）本篇主要介紹了克魯斯卡爾算法編寫中需要處理的三個問題，排序、查找和合並
（2）復雜的函數都是由簡單的函數構造而成的，我們可以把算法分成幾個獨立的部分，各個擊破
（3）解決了這三個問題，下一篇博客就可以進行歸總分析處理，邏輯上也十分清晰了
