程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 一步一步寫算法(之prim算法 中)

一步一步寫算法(之prim算法 中)

編輯:關於C

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱: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)算法只要能夠按照手工計算的流程編寫出來,基本上問題不大,但是一些細節還是要小心注意的

 

 

 

 

 

【待續】

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved