一步一步写算法（之克鲁斯卡尔算法 中）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：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 ++;
}
}
补充：软件开发 , C语言 ,
