Prim 演算法完整實作（中）：最小生成樹建構與邊選擇核心邏輯

前言

本文為 Prim 演算法系列第二篇，聚焦於「最小生成樹建構主流程」與「邊選擇核心函數」的實作細節，展示自頂向下的模組化設計思路。

主流程：get_mini_tree_from_graph

函數負責協調整個生成過程：初始化樹結構 → 迴圈尋找最佳邊 → 加入樹中 → 直到無有效邊為止。

MINI_GENERATE_TREE* get_mini_tree_from_graph(GRAPH* pGraph) {
    if (!pGraph || !pGraph->head) return NULL;

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

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

    while (1) {
        DIR_LINE dirLine;
        memset(&dirLine, 0, sizeof(DIR_LINE));
        get_dir_line_from_graph(pGraph, pMiniTree, &dirLine);
        if (dirLine.start == 0) break;  // 無可用邊

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

核心子函數 1：邊選擇 get_dir_line_from_graph

此函數完成「從當前樹的所有節點出發，收集所有鄰接邊 → 過濾無效 → 排序 → 取最小」的完整流程：

void get_dir_line_from_graph(GRAPH* pGraph, MINI_GENERATE_TREE* pMiniTree, DIR_LINE* pDirLine) {
    DIR_LINE* pHead = NULL;

    // 1. 收集所有候選邊
    for (int i = 0; i < pMiniTree->node_num; i++) {
        int start = pMiniTree->pNode[i];
        VECTEX* pVectex = find_vectex_in_graph(pGraph->head, start);
        LINE* pLine = pVectex->neighbor;
        while (pLine) {
            insert_line_into_queue(&pHead, start, pLine->end, pLine->weight);
            pLine = pLine->next;
        }
    }

    if (!pHead) return;

    // 2. 過濾無效邊（兩端點皆在樹中）
    delete_unvalid_line_from_list(&pHead, pMiniTree);
    if (!pHead) return;

    // 3. 排序並取最小
    sort_for_line_list(&pHead);
    memmove(pDirLine, pHead, sizeof(DIR_LINE));

    // 4. 釋放暫存鏈表
    while (pHead) {
        DIR_LINE* prev = pHead;
        pHead = pHead->next;
        free(prev);
    }
}

核心子函數 2：節點加入 insert_node_into_mini_tree

將新邊的「未在樹中」端點加入節點陣列：

void insert_node_into_mini_tree(DIR_LINE* pLine, MINI_GENERATE_TREE* pMiniTree) {
    for (int i = 0; i < pMiniTree->node_num; i++) {
        if (pLine->start == pMiniTree->pNode[i]) {
            pMiniTree->pNode[pMiniTree->node_num++] = pLine->end;
            return;
        }
    }
    // start 不在樹中，則加入 start
    pMiniTree->pNode[pMiniTree->node_num++] = pLine->start;
}

設計備註

• 函數 get_dir_line_from_graph 中呼叫的 delete_unvalid_line_from_list、sort_for_line_list 將在下篇詳述。
• 自頂向下設計雖然主流程先行，但子函數缺失會導致編譯失敗；建議以「存根」先行編譯通過，再逐個填實。
• 演算法邏輯源自手工模擬，只要流程正確、細節謹慎（如記憶體釋放、指標邊界），通常不會有大問題。