一步一步寫算法（之prim算法 中）

 

【 聲明：版權所有，歡迎轉載，請勿用於商業用途。  聯系信箱：feixiaoxing @163.com】

 

 

 

 

    C）編寫最小生成樹，涉及創建、挑選和添加過程

 

 

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; 

} 

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） 構建挑選函數，選擇最合適的邊

 

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; 

} 

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）添加節點函數，將尚不是最小生成樹的點納入到最小生成樹當中去

 

 

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; 

} 

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;

}

注意事項：

 

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

 

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

 

    （3）d中的函數delete_unvalid_line_from_list、sort_for_line_list會在下一篇中繼續介紹

 

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

 

 

 

 

 

【待續】