Prim 算法求最小生成樹：從鄉鎮通網到 C 語言完整實現（上）

一、最小生成樹：現實問題的數學抽象

場景：某鄉鎮有 n 個村莊，需鋪設光纖實現「村村通」。現有道路網絡可抽象為帶權無向圖，邊權為鋪設成本。目標：連通所有村莊且總成本最小 → 求圖的最小生成樹（MST）。

MST 定義：包含圖中所有頂點、n-1 條邊、無環、邊權和最小的連通子圖。

二、Prim 算法核心思想：貪心擴展

1. 初始化：任選一頂點加入集合 U
2. 候選邊集：維護所有「一端在 U，一端不在 U」的邊
3. 貪心選擇：從候選邊中選權值最小的邊 (u,v)，將 v 加入 U
4. 更新候選集：加入 v 後，將 v 發出的所有邊加入候選集（去除指向 U 內頂點的邊）
5. 重複 直到 U 包含所有頂點

關鍵數據結構：優先隊列（最小堆）維護候選邊，實現 O(E log V) 複雜度。

三、數據結構設計

// 生成樹邊：有向邊記錄起點、終點、權重
typedef struct _DIR_LINE {
    int start, end, weight;
    struct _DIR_LINE* next;
} DIR_LINE;

// 最小生成樹結果結構
typedef struct _MINI_GENERATE_TREE {
    int node_num;      // 頂點數
    int line_num;      // 邊數
    int* pNode;        // 包含的頂點集合
    DIR_LINE* pLine;   // 生成樹邊鏈表
} MINI_GENERATE_TREE;

四、輔助隊列操作：候選邊管理

// 插入邊到候選隊列（頭插法）
STATUS insert_line_into_queue(DIR_LINE** ppLine, int start, int end, int weight) {
    if (!ppLine) return FALSE;
    
    DIR_LINE* pLine = create_new_dir_line(start, end, weight);
    if (!pLine) return FALSE;
    
    pLine->next = *ppLine;
    *ppLine = pLine;
    return TRUE;
}

// 從候選隊列刪除指定邊
STATUS delete_line_from_queue(DIR_LINE** ppLine, DIR_LINE* pTarget) {
    if (!ppLine || !*ppLine || !pTarget) return FALSE;
    
    DIR_LINE* prev = NULL;
    DIR_LINE* curr = *ppLine;
    
    while (curr && curr != pTarget) {
        prev = curr;
        curr = curr->next;
    }
    if (!curr) return FALSE;  // 未找到
    
    if (prev) prev->next = curr->next;
    else *ppLine = curr->next;
    
    free(curr);
    return TRUE;
}

五、Prim 算法主流程框架

MINI_GENERATE_TREE* prim_mst(GRAPH* graph, int start_vertex) {
    // 1. 初始化
    MINI_GENERATE_TREE* mst = malloc(sizeof(MINI_GENERATE_TREE));
    mst->node_num = 1;
    mst->line_num = 0;
    mst->pNode = malloc(graph->count * sizeof(int));
    mst->pNode[0] = start_vertex;
    mst->pLine = NULL;
    
    DIR_LINE* candidate_edges = NULL;  // 候選邊鏈表
    int* in_mst = calloc(graph->count, sizeof(int));  // 標記已加入頂點
    in_mst[start_vertex] = 1;
    
    // 2. 將起始頂點所有邊加入候選集
    VECTEX* v = find_vectex_in_graph(graph->head, start_vertex);
    for (LINE* e = v->neighbor; e; e = e->next) {
        insert_line_into_queue(&candidate_edges, start_vertex, e->end, e->weight);
    }
    
    // 3. 主循環：選擇 n-1 條邊
    while (mst->line_num < graph->count - 1 && candidate_edges) {
        // 3.1 找最小邊（線性掃描，堆優化見下文）
        DIR_LINE *min_edge = candidate_edges, *prev = NULL, *curr = candidate_edges;
        DIR_LINE *min_prev = NULL;
        
        while (curr) {
            if (curr->weight < min_edge->weight) {
                min_edge = curr;
                min_prev = prev;
            }
            prev = curr;
            curr = curr->next;
        }
        
        // 3.2 檢查目標頂點是否已在 MST 中
        if (in_mst[min_edge->end]) {
            // 目標已在樹中，丟棄此邊
            delete_line_from_queue(&candidate_edges, min_edge);
            continue;
        }
        
        // 3.3 加入 MST
        delete_line_from_queue(&candidate_edges, min_edge);
        insert_line_into_queue(&mst->pLine, min_edge->start, min_edge->end, min_edge->weight);
        mst->pNode[mst->node_num++] = min_edge->end;
        mst->line_num++;
        in_mst[min_edge->end] = 1;
        
        // 3.4 擴展候選集：加入新頂點的所有邊
        VECTEX* new_v = find_vectex_in_graph(graph->head, min_edge->end);
        for (LINE* e = new_v->neighbor; e; e = e->next) {
            if (!in_mst[e->end]) {
                insert_line_into_queue(&candidate_edges, min_edge->end, e->end, e->weight);
            }
        }
    }
    
    free(in_mst);
    return (mst->line_num == graph->count - 1) ? mst : NULL;  // 圖不連通返回 NULL
}

六、關鍵優化：最小堆實現 O(E log V)

上述線性掃描找最小邊為 O(E)，總複雜度 O(VE)。使用二叉最小堆優化：

typedef struct {
    DIR_LINE** heap;  // 指針數組
    int size, capacity;
} MinHeap;

// 堆操作：push、pop_min、decrease_key（需支持更新邊權重）
// 實現細節見「下篇：堆優化版完整代碼」

七、算法正確性證明要點

1. 切割性質：任意切割圖頂點集，權最小的橫切邊必在某 MST 中
2. Prim 邀請機制：每步選擇的邊正是當前切割 (U, V-U) 的最小橫切邊
3. 歸納法：每步保持已選邊集可擴展為某 MST

八、與 Kruskal 算法對比

九、工程應用場景

• 網絡佈線（光纖、電纜、管道）
• 電路板佈線優化
• 聚類分析（歐氏距離構建完全圖，MST 切除長邊得聚類）
• 圖像分割（像素為點，顏色差為權）
• 近似算法基石（TSP 2-近似、Steiner Tree 等）

下篇預告：最小堆優化完整代碼、處理不連通圖、邊權更新優化、並行 Prim 算法思路。