1、 一步一步寫算法（之克魯斯卡爾算法 中）【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。  聯(lián)系信箱：feixiaoxing 】    前面說(shuō)到，克魯斯卡爾的算法是按照各個(gè)line的權(quán)重依次進(jìn)行添加的，那么這就涉及到一個(gè)權(quán)重的排序問題。怎么排序呢？可以采用最簡(jiǎn)單的冒泡排序算法?？墒沁@里排序的是數(shù)據(jù)結(jié)構(gòu)，怎么辦呢？那就只好采用通用排序算法了。cpp view plaincopy1. void bubble_sort(void* array, int length, int (*

2、compare)(void*, void*), void(*swap)(void*, void*)  2.   3.     int outer;  4.     int inner;  5.       6.     for(outer = length -

3、1; outer >0; outer -)  7.         for(inner = 0; inner < outer; inner +)  8.             if(compare(arrayinner, ar

4、rayinner + 1)  9.                 swap(&arrayinner, &arrayinner + 1);  10.           11.     

5、0; 12.       13.     return;  14.       所以，這里就要添加上屬于DIR_LINE的compare和swap函數(shù)，cpp view plaincopy1. int compare(void* data1, void* data2)  2.   3.    

6、60;DIR_LINE* line1 = (DIR_LINE*) data1;  4.     DIR_LINE* line2 = (DIR_LINE*) data2;  5.       6.     return (line1->weight > line2->weight) 

7、? 1 : 0;  7.   8.   9. void swap(void* data1, void* data2)  10.   11.     DIR_LINE* median;  12.     DIR_LINE* line1;  13.    

8、0;DIR_LINE* line2;  14.   15.     line1 = (DIR_LINE*) data1;  16.     line2 = (DIR_LINE*) data2;  17.   18.     median = *line1;  19. &

9、#160;   *line1 = *line2;  20.     *line2 = median;  21.       排序結(jié)束之后，我們就開始線段的插入工作，那么進(jìn)行線段插入的時(shí)候，我們需要知道當(dāng)前線段是不是在某一個(gè)最小生成樹中已經(jīng)存在了，如果是這樣的話，那么這個(gè)線段就要被忽略了。所以，這中間還存在一個(gè)判斷的問題，cpp view plaincopy1. int getV

10、ectexNumFromTree(MINI_GENERATE_TREE* pTree, int start, int end)  2.   3.     int index;  4.     int total;  5.   6.     total = 0;  7.

11、    for(index = 0; index < pTree->node_num; index+)  8.         if(start = pTree->pNodeindex)  9.             t

12、otal +;  10.             continue;  11.           12.   13.         if(end = pTree->pNodeindex) &

13、#160;14.             total +;  15.           16.       17.   18.     return total;  19.   

14、20.   21. int isDoubleVectexExistInTree(MINI_GENERATE_TREE* pTree, int length, int start, int end)  22.   23.     int index = 0;  24.     int value = 

15、0;  25.     int number = 0;  26.   27.     for(index = 0; index < length; index +)  28.         number = getVectexNum

16、FromTree(pTreeindex, start, end);  29.   30.         if(number > value)  31.             value = number;  32.    

17、;   33.   34.   35.     return (value = 2) ? 1 : 0;  36.       線段的判斷之后，如果發(fā)現(xiàn)在兩顆獨(dú)立的最小生成樹上面，那么還需要進(jìn)行合并操作，刪除其中一個(gè)最小生成樹，把另外一個(gè)生成樹的所有點(diǎn)和線段都要添加到?jīng)]有刪除的這顆最小生成樹上面。當(dāng)然還有一點(diǎn)不要忘記了，最后還要加上端口分別在兩棵樹上

18、的這個(gè)線段。cpp view plaincopy1. void  mergeTwoMiniGenerateTree(MINI_GENERATE_TREE* pTree, int length, int start, int end, int weight)  2.   3.     MINI_GENERATE_TREE* pFirst;  4.   

19、;  MINI_GENERATE_TREE* pSec;  5.     DIR_LINE* line;  6.     int index;  7.   8.     /* 刪除多余的最小生成樹 */  9.     pFirst = find_t

20、ree_by_index(pTree, length, start);  10.     pSec = find_tree_by_index(pTree, length, end);  11.     delete_mini_tree_from_group(pTree, length, pSec);  12.   13.    

21、 /* 合并節(jié)點(diǎn) */  14.     for(index = 0; index < pSec->node_num; index +)  15.         pFirst->pNodepFirst->node_num + index = pSec->pNodeindex;  16.       17.     pFirst->node_num += pSec->node_num;  18.   19.     /* 合并線段 */  20.     for(line = pSec-