手把手寫演算法：Prim 最小生成樹完整實現（中）

編輯：關於C語言

承接上篇，我們繼續自頂向下實現 Prim 演算法求最小生成樹 (MST)。本篇完成核心框架的三大關鍵函數：建樹主流程、邊選擇策略、節點加入機制。

資料結構回顧

typedef struct _DIR_LINE {  // 有向邊
    int start, end, weight;
    struct _DIR_LINE* next;
} DIR_LINE;

typedef struct _MINI_GENERATE_TREE {  // 最小生成樹
    int node_num, line_num;
    int* pNode;        // 節點陣列
    DIR_LINE* pLine;   // 邊鏈表
} MINI_GENERATE_TREE;

typedef struct _GRAPH {  // 圖
    int count;
    VECTEX* head;
} GRAPH;

C. 建樹主流程 `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 = (MINI_GENERATE_TREE*)malloc(sizeof(MINI_GENERATE_TREE));
    assert(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) {
        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;
}

核心邏輯：初始化樹結構 → 從起始節點出發 → 循環尋找連接樹內節點與樹外節點的最小權重邊 → 加入邊與新節點 → 直到無法擴展。

D. 邊選擇策略 `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);
        for (LINE* pLine = pVectex->neighbor; pLine; pLine = pLine->next)
            insert_line_into_queue(&pHead, start, pLine->end, pLine->weight);
    }
    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);
    }
}

此函數完成「候選邊收集 → 過濾 → 排序 → 取最小」完整流程，體現 Prim 演算法「貪婪選擇最小權重邊」的核心思想。

E. 節點加入機制 `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;
        }
    }
    // 否則加入起點（理論上不應發生，但作為防禦性編程）
    pMiniTree->pNode[pMiniTree->node_num++] = pLine->start;
}

由於 get_dir_line_from_graph 已過濾雙端點在樹內的邊，新邊必有一端點在樹外，此函數將該外部節點納入樹中。