武侠 电影粤语:一步一步写算法（之克鲁斯卡尔算法 中）

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

前面说到，克鲁斯卡尔的算法是按照各个line的权重依次进行添加的，那么这就涉及到一个权重的排序问题。怎么排序呢？可以采用最简单的冒泡排序算法。可是这里排序的是数据结构，怎么办呢？那就只好采用通用排序算法了。

view plaincopy to clipboardprint?

1. void bubble_sort(void* array[], int length, int (*compare)(void*, void*), void(*swap)(void**, void**))
2. {
3. int outer;
4. int inner;
6. for(outer = length -1; outer >0; outer --){
7. for(inner = 0; inner < outer; inner ++){
8. if(compare(array[inner], array[inner + 1]))
9. swap(&array[inner], &array[inner + 1]);
10. }
11. }
13. return;
14. }

view plaincopy to clipboardprint?

1. int compare(void* data1, void* data2)
2. {
3. DIR_LINE* line1 = (DIR_LINE*) data1;
4. DIR_LINE* line2 = (DIR_LINE*) data2;
6. return (line1->weight > line2->weight) ? 1 : 0;
7. }
9. void swap(void** data1, void** data2)
10. {
11. DIR_LINE* median;
12. DIR_LINE** line1;
13. DIR_LINE** line2;
15. line1 = (DIR_LINE**) data1;
16. line2 = (DIR_LINE**) data2;
18. median = *line1;
19. *line1 = *line2;
20. *line2 = median;
21. }

view plaincopy to clipboardprint?

1. int getVectexNumFromTree(MINI_GENERATE_TREE* pTree, int start, int end)
2. {
3. int index;
4. int total;
6. total = 0;
7. for(index = 0; index < pTree->node_num; index++){
8. if(start == pTree->pNode[index]){
9. total ++;
10. continue;
11. }
13. if(end == pTree->pNode[index]){
14. total ++;
15. }
16. }
18. return total;
19. }
21. int isDoubleVectexExistInTree(MINI_GENERATE_TREE* pTree[], int length, int start, int end)
22. {
23. int index = 0;
24. int value = 0;
25. int number = 0;
27. for(index = 0; index < length; index ++){
28. number = getVectexNumFromTree(pTree[index], start, end);
30. if(number > value)
31. value = number;
32. }
35. return (value == 2) ? 1 : 0;
36. }

view plaincopy to clipboardprint?

1. void mergeTwoMiniGenerateTree(MINI_GENERATE_TREE* pTree[], int length, int start, int end, int weight)
2. {
3. MINI_GENERATE_TREE* pFirst;
4. MINI_GENERATE_TREE* pSec;
5. DIR_LINE* line;
6. int index;
8. /* 删除多余的最小生成树 */
9. pFirst = find_tree_by_index(pTree, length, start);
10. pSec = find_tree_by_index(pTree, length, end);
11. delete_mini_tree_from_group(pTree, length, pSec);
13. /* 合并节点 */
14. for(index = 0; index < pSec->node_num; index ++){
15. pFirst->pNode[pFirst->node_num + index] = pSec->pNode[index];
16. }
17. pFirst->node_num += pSec->node_num;
19. /* 合并线段 */
20. for(line = pSec->pLine; line; line = line->next){
21. insert_line_into_queue(&pFirst->pLine, line->start, line->end, line->weight);
22. }
23. insert_line_into_queue(&pFirst->pLine, start, end, weight);
25. /* 函数返回 */
26. return;
27. }

（1）本篇主要介绍了克鲁斯卡尔算法编写中需要处理的三个问题，排序、查找和合并

（2）复杂的函数都是由简单的函数构造而成的，我们可以把算法分成几个独立的部分，各个击破

（3）解决了这三个问题，下一篇博客就可以进行归总分析处理，逻辑上也十分清晰了

【未完，待续】