C）編寫最小生成樹，涉及創(chuàng)建、挑選和添加過(guò)程

MINI_GENERATE_TREE* get_mini_tree_from_graph(GRAPH* pGraph)
{
    MINI_GENERATE_TREE* pMiniTree;
    DIR_LINE pDirLine;

    if(NULL == pGraph || NULL == pGraph->head)
        return NULL;

    pMiniTree = (MINI_GENERATE_TREE*)malloc(sizeof(MINI_GENERATE_TREE));
    assert(NULL != pMiniTree);
    memset(pMiniTree, 0, sizeof(MINI_GENERATE_TREE));

    pMiniTree->node_num = 1;
    pMiniTree->pNode = (int*)malloc(sizeof(int) * pGraph->count);
    memset(pMiniTree->pNode, 0, sizeof(int) * pGraph->count);
    pMiniTree->pNode[0] = pGraph->head->start;

    while(1){
        memset(&pDirLine, 0, sizeof(DIR_LINE));
        get_dir_line_from_graph(pGraph, pMiniTree, &pDirLine);
        if(pDirLine.start == 0)
            break;

        pMiniTree->line_num ++;
        insert_line_into_queue(&pMiniTree->pLine, pDirLine.start, pDirLine.end, pDirLine.weight);
        insert_node_into_mini_tree(&pDirLine, pMiniTree);
    }

    return pMiniTree;
}

d） 構(gòu)建挑選函數(shù)，選擇最合適的邊

void get_dir_line_from_graph(GRAPH* pGraph, MINI_GENERATE_TREE* pMiniTree, DIR_LINE* pDirLine)
{
    DIR_LINE* pHead;
    DIR_LINE* prev;
    VECTEX* pVectex;
    LINE* pLine;
    int index;
    int start;

    pHead = NULL;
    for(index = 0; index < pMiniTree->node_num; index++){
        start = pMiniTree->pNode[index];
        pVectex = find_vectex_in_graph(pGraph->head, start);
        pLine = pVectex->neighbor;

        while(pLine){
            insert_line_into_queue(&pHead, start, pLine->end, pLine->weight);
            pLine = pLine->next;
        }
    }

    if(NULL == pHead)
        return;

    delete_unvalid_line_from_list(&pHead, pMiniTree);
    if(NULL == pHead)
        return;

    sort_for_line_list(&pHead);
    memmove(pDirLine, pHead, sizeof(DIR_LINE));

    while(pHead){
        prev = pHead;
        pHead = pHead->next;
        free(prev);
    }
    return;
}

e）添加節(jié)點(diǎn)函數(shù)，將尚不是最小生成樹的點(diǎn)納入到最小生成樹當(dāng)中去

void insert_node_into_mini_tree(DIR_LINE* pLine, MINI_GENERATE_TREE* pMiniTree)
{
    int index;

    for(index = 0; index < pMiniTree->node_num; index ++){
        if(pLine->start == pMiniTree->pNode[index]){
            pMiniTree->pNode[pMiniTree->node_num++] = pLine->end;
            return;
        }
    }

    pMiniTree->pNode[pMiniTree->node_num++] = pLine->start;
    return;
}

注意事項(xiàng)：

（1）d、e是c中調(diào)用的子函數(shù)，如果大家觀察一下就明白了

（2）最小生成樹是按照自頂向下的順序編寫的，雖然c中的子函數(shù)完成了，但是d中還有兩個(gè)子函數(shù)沒有著落

（3）d中的函數(shù)delete_unvalid_line_from_list、sort_for_line_list會(huì)在下一篇中繼續(xù)介紹

（4）算法只要能夠按照手工計(jì)算的流程編寫出來(lái)，基本上問題不大，但是一些細(xì)節(jié)還是要小心注意的