一步一步写算法之克鲁斯卡尔算法 中

1、 一步一步写算法（之克鲁斯卡尔算法 中）【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing 】    前面说到，克鲁斯卡尔的算法是按照各个line的权重依次进行添加的，那么这就涉及到一个权重的排序问题。怎么排序呢？可以采用最简单的冒泡排序算法。可是这里排序的是数据结构，怎么办呢？那就只好采用通用排序算法了。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函数，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.       排序结束之后，我们就开始线段的插入工作，那么进行线段插入的时候，我们需要知道当前线段是不是在某一个最小生成树中已经存在了，如果是这样的话，那么这个线段就要被忽略了。所以，这中间还存在一个判断的问题，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.       线段的判断之后，如果发现在两颗独立的最小生成树上面，那么还需要进行合并操作，删除其中一个最小生成树，把另外一个生成树的所有点和线段都要添加到没有删除的这颗最小生成树上面。当然还有一点不要忘记了，最后还要加上端口分别在两棵树上

18、的这个线段。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、 /* 合并节点 */  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-