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

承接前兩篇，本文完善 Prim 演算法最後兩個關鍵子函數：無效邊過濾與鏈表排序，並總結完整實現心得。

F. 無效邊過濾 delete_unvalid_line_from_list

移除雙端點皆已在最小生成樹中的邊，避免形成環。

void delete_unvalid_line_from_list(DIR_LINE** ppHead, MINI_GENERATE_TREE* pMiniTree) {
    DIR_LINE *prev = NULL, *pcur = *ppHead;
    while (pcur) {
        if (!check_valid_for_line(pcur, pMiniTree)) {  // 雙端點都在樹中
            STATUS result = delete_line_from_queue(ppHead, pcur);
            assert(TRUE == result);
            pcur = (prev == NULL) ? *ppHead : prev->next;  // 刪除後調整游標
            continue;
        }
        prev = pcur;
        pcur = pcur->next;
    }
}

關鍵點：刪除節點後需正確更新遍歷指標。若刪除頭節點 (prev == NULL)，pcur 重置為新頭節點；否則指向 prev->next。

G. 邊有效性檢查 check_valid_for_line

判斷邊是否連接樹內與樹外節點（異或邏輯：一在一不在）。

int check_valid_for_line(DIR_LINE* pDirLine, MINI_GENERATE_TREE* pMiniTree) {
    int flag_start = 0, flag_end = 0;
    for (int i = 0; i < pMiniTree->node_num; i++) {
        if (pDirLine->start == pMiniTree->pNode[i]) { flag_start = 1; break; }
    }
    for (int i = 0; i < pMiniTree->node_num; i++) {
        if (pDirLine->end == pMiniTree->pNode[i]) { flag_end = 1; break; }
    }
    return (flag_start && flag_end) ? 0 : 1;  // 雙在樹內→無效(0)，否則有效(1)
}

優化建議：可合併為單次遍歷，用位標記同時檢查兩端點。

H. 鏈表插入排序 sort_for_line_list

對候選邊按權重升序排列，採用插入排序構建有序鏈表。

void insert_for_sort_operation(DIR_LINE** ppNode, DIR_LINE* pNode) {
    // 插入到頭部
    if (pNode->weight < (*ppNode)->weight) {
        pNode->next = *ppNode;
        *ppNode = pNode;
        return;
    }
    // 尋找插入位置
    DIR_LINE *prev = *ppNode, *cur = (*ppNode)->next;
    while (cur && pNode->weight >= cur->weight) {
        prev = cur;
        cur = cur->next;
    }
    pNode->next = prev->next;
    prev->next = pNode;
}

void sort_for_line_list(DIR_LINE** ppNode) {
    if (!ppNode || !*ppNode) return;
    DIR_LINE* curr = (*ppNode)->next;
    (*ppNode)->next = NULL;  // 截斷原鏈表，首節點作為有序鏈表初始狀態
    while (curr) {
        DIR_LINE* prev = curr;
        curr = curr->next;
        insert_for_sort_operation(ppNode, prev);  // 逐個插入有序鏈表
    }
}

演算法優勢：原地排序、空間 O(1)、對部份有序資料效率高、穩定排序。

Prim 演算法完整實現總結

優化方向與心得

1. 記憶體分配優化：每輪重建候選邊鏈表頻繁 malloc/free，可改用靜態陣列或記憶體池
2. 時間複雜度：現實現 O(V·E)，採用優先佇列 (Min-Heap) 可優化至 O(E log V)
3. 開發流程：自頂向下分解 → 單元測試 → 整合測試 → 重構優化，預期反覆修改 4-5 次屬正常
4. 代碼復用：排序、鏈表、圖遍歷等基礎組件應建立個人代碼庫

三篇文章完整呈現了從演算法理解到工程實現的全過程。掌握這套「分解-實現-驗證-優化」方法論，可應用於任意圖論演算法的工程化落地。