bo shanghai 招聘:一步一步写算法（之克鲁斯卡尔算法 下）

一步一步写算法（之克鲁斯卡尔算法 下）

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

    前面在讨论克鲁斯卡尔的算法的时候，我们分析了算法的基本过程、基本数据结构和算法中需要解决的三个问题（排序、判断、合并）。今天，我们继续完成剩下部分的内容。合并函数中，我们调用了两个基本函数，find_tree_by_index和delete_mini_tree_from_group，下面给出详细的计算过程。

1. MINI_GENERATE_TREE* find_tree_by_index(MINI_GENERATE_TREE* pTree[], int length, int point)  
2. {  
3.     int outer;  
4.     int inner;  
5.   
6.     for(outer = 0; outer < length; outer++){  
7.         for(inner = 0; inner < pTree[outer]->node_num; inner ++){  
8.             if(point == pTree[outer]->pNode[inner])  
9.                 return pTree[outer];  
10.         }  
11.     }  
12.   
13.     return NULL;  
14. }  
15.   
16. void delete_mini_tree_from_group(MINI_GENERATE_TREE* pTree[], int length, MINI_GENERATE_TREE* pIndex)  
17. {  
18.     int index;  
19.   
20.     for(index = 0; index < length; index ++){  
21.         if(pIndex == pTree[index])  
22.             break;  
23.     }  
24.   
25.     memmove(&pTree[index +1], &pTree[index], sizeof(MINI_GENERATE_TREE*) * (length -1 - index));  
26.     return;  
27. }  

1. MINI_GENERATE_TREE* _kruskal(MINI_GENERATE_TREE* pTree[], int length, DIR_LINE* pLine[], int number)  
2. {  
3.     int index;  
4.       
5.     if(NULL == pTree || NULL == pLine)  
6.         return NULL;  
7.       
8.     for(index = 0; index < number; index ++){  
9.           
10.         bubble_sort((void**)pLine, number, compare, swap);  
11.           
12.         if(2 == isDoubleVectexExistInTree(pTree, length, pLine[index]->start, pLine[index]->end))  
13.             continue;  
14.           
15.         mergeTwoMiniGenerateTree(pTree, length, pLine[index]->start, pLine[index]->end, pLine[index]->weight);  
16.         length --;  
17.     }  
18.       
19.     return (1 != length) ? NULL : pTree[0];  
20. }  

1. MINI_GENERATE_TREE* kruskal(GRAPH* pGraph)  
2. {  
3.     MINI_GENERATE_TREE** pTree;  
4.     DIR_LINE** pLine;  
5.     int count;  
6.     int number;  
7.   
8.     if(NULL == pGraph)  
9.         return NULL;  
10.   
11.     count = pGraph->count;  
12.     number = get_total_line_number(pGraph);  
13.   
14.     pTree = get_tree_from_graph(pGraph);  
15.     pLine = get_line_from_graph(pGraph);  
16.   
17.     return _kruskal(pTree, count, pLine, number);  
18. }  

总结：

    （1）代码中没有考虑内存的释放问题，需要改进和提高

    （2）部分代码可以复用prim算法中的内容，数据结构也一样

    （3）算法的编写贵在理解，只要步骤对了，再加上测试，一般问题都不大