Prim 演算法完整實作（下）：關鍵輔助函數與優化總結

前言

承接前兩篇，本文完成 Prim 演算法的最後拼圖：無效邊清理、邊合法性判斷、鏈表排序三大核心輔助函數，並給出演算法工程化的四點心得。

核心輔助函數詳解

1. 清理無效邊 delete_unvalid_line_from_list

遍歷邊鏈表，呼叫 check_valid_for_line 判斷；若無效則從鏈表移除並釋放記憶體。注意指標操作需處理頭節點刪除與中間節點刪除兩種情況。

void delete_unvalid_line_from_list(DIR_LINE** ppHead, MINI_GENERATE_TREE* pMiniTree) {
    DIR_LINE* prev = NULL;
    DIR_LINE* pcur = *ppHead;
    while (pcur) {
        if (!check_valid_for_line(pcur, pMiniTree)) {
            // 刪除當前節點
            DIR_LINE* toDel = pcur;
            if (prev == NULL) {
                *ppHead = pcur->next;
                pcur = *ppHead;
            } else {
                prev->next = pcur->next;
                pcur = prev->next;
            }
            free(toDel);
            continue;
        }
        prev = pcur;
        pcur = pcur->next;
    }
}

2. 邊合法性判斷 check_valid_for_line

檢查邊的起點、終點是否「至少有一個」不在當前生成樹中。若兩者皆在樹中 → 會形成環 → 無效 (回傳 0)；否則有效 (回傳 1)。

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;
        if (pDirLine->end == pMiniTree->pNode[i]) flag_end = 1;
    }
    return (flag_start && flag_end) ? 0 : 1;
}

3. 鏈表插入排序 sort_for_line_list + insert_for_sort_operation

採用「線上插入排序」：將原鏈表拆解，逐節點插入新有序鏈表。適合動態產生邊的場景，避免陣列排序的額外空間。

void insert_for_sort_operation(DIR_LINE** ppNode, DIR_LINE* pNode) {
    if (pNode->weight < (*ppNode)->weight) {
        pNode->next = *ppNode;
        *ppNode = pNode;
        return;
    }
    DIR_LINE* cur = *ppNode;
    DIR_LINE* prev = NULL;
    while (cur) {
        if (pNode->weight < cur->weight) break;
        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);
    }
}

演算法工程化心得

1. 記憶體策略可優化：每次迭代重建 DIR_LINE 隊列會有分配/釋放開銷，可考慮記憶體池或靜態陣列複用。
2. 代碼非一次成型：複雜演算法常需反覆修改 4-5 版，保持耐心、小步快跑。
3. 邊寫邊測：單元測試同步進行，既能捕捉邊界錯誤，又能建立信心。
4. 善用成熟基礎庫：排序、堆疊、二叉樹等通用模組應積累復用，避免重複造輪子。

完整流程回顧

Prim 演算法主流程：

MINI_GENERATE_TREE* get_mini_tree_from_graph(GRAPH* pGraph) {
    MINI_GENERATE_TREE* pMiniTree = malloc(sizeof(MINI_GENERATE_TREE));
    // 初始化：放入第一個節點
    pMiniTree->node_num = 1;
    pMiniTree->pNode[0] = pGraph->head->start;

    while (1) {
        DIR_LINE bestEdge;
        get_dir_line_from_graph(pGraph, pMiniTree, &bestEdge);
        if (bestEdge.start == 0) break;  // 無有效邊 → 完成

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

其中 get_dir_line_from_graph 內部串聯：收集候選邊 → 清理無效 → 排序 → 取最小 → 釋放暫存鏈表。