C++算法之克鲁斯卡尔算法

克鲁斯卡尔算法是计算最小生成树的一种算法。和prim算法（上，中，下）按照节点进行查找的方法不一样，克鲁斯卡尔算法是按照具体的线段进行的。现在我 们假设一个图有m个节点，n条边。首先，我们需要把m个节点看成m个独立的生成树，并且把n条边按照从小到大的数据进行排列。在n条边中，我们依次取出其 中的每一条边，如果发现边的两个节点分别位于两棵树上，那么把两棵树合并成为一颗树；如果树的两个节点位于同一棵树上，那么忽略这条边，继续运行。等到所 有的边都遍历结束之后，如果所有的生成树可以合并成一条生成树，那么它就是我们需要寻找的最小生成树，反之则没有最小生成树。 ????

上面的算法可能听上去有些费解，我们可以用一个示例说明一下，

/* 
*          9 
*    D ----------- 
*  3 |           | 
*    |      6    | 
*    A  -------  B  
*    |           | 
*    |   7       | 5 
*    -------C---- 
**/  

????现在有这么4个点。其中?A-D?为3，?A-C为7，A-B为6，B-D为9，B-C为5，下面就开始计算，我们首先默认所有的点都是单独的最小生成树，

/* 
*           
*    D  
*          
*    A           B  
*          
*          C 
**/  

????第一步，按照从小到大的顺序，我们加入最小的边A-D，

/* 
*           
*    D  
*  3 |       
*    |       
*    A           B  
* 
* 
*           C 
**/  

????然后，我们发现下面最小的边是B-C，

/* 
*           
*    D  
*  3 |       
*    |       
*    A           B  
*                | 
*                | 5 
*           C---- 
**/  

????接着，我们发现最小的边是A-B，因为点A和点B位于不同的最小生成树上面，所以继续合并，

/*           
*    D  
*  3 |       
*    |     6  
*    A---------- B  
*                | 
*                | 5 
*           C---- 
**/  

????接下来，我们还会遍历A-C，B-D，但是我们发现此时边的节点都已经遍历过了，所以均忽略，最小生成树的结构就是上面的内容。
????那么最小生成树的数据结构是什么，应该怎么定义，不知道朋友们还记得否？我们曾经在prim算法中讨论过，

/* 直连边 */  
typedef struct _DIR_LINE  
{  
    int start;  
    int end;  
    int weight;  
    struct _DIR_LINE* next;  
}DIR_LINE;  
  
/* 最小生成树 */  
typedef struct _MINI_GENERATE_TREE  
{  
    int node_num;  
    int line_num;  
    int* pNode;  
    DIR_LINE* pLine;  
}MINI_GENERATE_TREE;  
  
/* 节点边信息 */  
typedef struct _LINE  
{  
    int end;  
    int weight;  
    struct _LINE* next;  
}LINE;  
  
/*节点信息*/  
typedef struct _VECTEX  
{  
    int start;  
    int number;  
    LINE* neighbor;  
    struct _VECTEX* next;  
}VECTEX;  
  
/* 图信息 */  
typedef struct _GRAPH  
{  
    int count;  
    VECTEX* head;  
}GRAPH;  

????前面说到，克鲁斯卡尔的算法是按照各个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;  
}  

????所以，这里就要添加上属于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 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 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;  
}  

????线段的判断之后，如果发现在两颗独立的最小生成树上面，那么还需要进行合并操作，删除其中一个最小生成树，把另外一个生成树的所有点和线段都要添加到没有删除的这颗最小生成树上面。当然还有一点不要忘记了，最后还要加上端口分别在两棵树上的这个线段。

void  mergeTwoMiniGenerateTree(MINI_GENERATE_TREE* pTree[],int end,int weight)  
{  
    MINI_GENERATE_TREE* pFirst;  
    MINI_GENERATE_TREE* pSec;  
    DIR_LINE* line;  
    int index;  
  
    /* 删除多余的最小生成树 */  
    pFirst = find_tree_by_index(pTree,length,start);  
    pSec = find_tree_by_index(pTree,end);  
    delete_mini_tree_from_group(pTree,pSec);  
  
    /* 合并节点 */  
    for(index = 0; index < pSec->node_num; index ++){  
        pFirst->pNode[pFirst->node_num + index] = pSec->pNode[index];  
    }  
    pFirst->node_num += pSec->node_num;  
  
    /* 合并线段 */  
    for(line = pSec->pLine; line; line = line->next){  
        insert_line_into_queue(&pFirst->pLine,line->start,line->end,line->weight);  
    }  
    insert_line_into_queue(&pFirst->pLine,end,weight);  
  
    /* 函数返回 */  
    return;  
}  

总结：
????（1）这部分主要介绍了克鲁斯卡尔算法编写中需要处理的三个问题，排序、查找和合并
????（2）复杂的函数都是由简单的函数构造而成的，我们可以把算法分成几个独立的部分，各个击破
????（3）解决了这三个问题，下一篇博客就可以进行归总分析处理，逻辑上也十分清晰了
????前面在讨论克鲁斯卡尔的算法的时候，我们分析了算法的基本过程、基本数据结构和算法中需要解决的三个问题（排序、判断、合并）。今天，我们继续完成剩下部分的内容。合并函数中，我们调用了两个基本函数，find_tree_by_index和delete_mini_tree_from_group，下面给出详细的计算过程。

MINI_GENERATE_TREE* find_tree_by_index(MINI_GENERATE_TREE* pTree[],int point)  
{  
    int outer;  
    int inner;  
  
    for(outer = 0; outer < length; outer++){  
        for(inner = 0; inner < pTree[outer]->node_num; inner ++){  
            if(point == pTree[outer]->pNode[inner])  
                return pTree[outer];  
        }  
    }  
  
    return NULL;  
}  
  
void delete_mini_tree_from_group(MINI_GENERATE_TREE* pTree[],MINI_GENERATE_TREE* pIndex)  
{  
    int index;  
  
    for(index = 0; index < length; index ++){  
        if(pIndex == pTree[index])  
            break;  
    }  
  
    memmove(&pTree[index +1],&pTree[index],sizeof(MINI_GENERATE_TREE*) * (length -1 - index));  
    return;  
}  

????下面就可以开始编写克鲁斯卡尔最小生成树了，代码如下所示，

MINI_GENERATE_TREE* _kruskal(MINI_GENERATE_TREE* pTree[],DIR_LINE* pLine[],int number)  
{  
    int index;  
      
    if(NULL == pTree || NULL == pLine)  
        return NULL;  
      
    for(index = 0; index < number; index ++){  
          
        bubble_sort((void**)pLine,number,compare,swap);  
          
        if(2 == isDoubleVectexExistInTree(pTree,pLine[index]->start,pLine[index]->end))  
            continue;  
          
        mergeTwoMiniGenerateTree(pTree,pLine[index]->end,pLine[index]->weight);  
        length --;  
    }  
      
    return (1 != length) ? NULL : pTree[0];  
}  

???要进行上面的计算，我们还需要算出顶点的个数，线段的个数，所以函数还需要进一步完善和补充，

MINI_GENERATE_TREE* kruskal(GRAPH* pGraph)  
{  
    MINI_GENERATE_TREE** pTree;  
    DIR_LINE** pLine;  
    int count;  
    int number;  
  
    if(NULL == pGraph)  
        return NULL;  
  
    count = pGraph->count;  
    number = get_total_line_number(pGraph);  
  
    pTree = get_tree_from_graph(pGraph);  
    pLine = get_line_from_graph(pGraph);  
  
    return _kruskal(pTree,count,pLine,number);  
}  
 

???这样，克鲁斯卡尔算法大体上算结束了，其中get_total_line_number、get_tree_from_graph、get_line_from_graph函数都比较简单，朋友们可以自己继续完成，但是要好好测试。


总结：
????（1）代码中没有考虑内存的释放问题，需要改进和提高
????（2）部分代码可以复用prim算法中的内容，数据结构也一样
????（3）算法的编写贵在理解，只要步骤对了，再加上测试，一般问题都不大