圖論算法實作：邊的添加與刪除完整指南

前言

在前幾篇文章中，我們已經探討了圖的資料結構定義與建立方法。今天要深入討論圖操作的核心——邊的動態添加與刪除。雖然邊的操作邏輯不算複雜，但關鍵在於「以小函數構建大功能」的模組化設計思維，這能有效避免指標操作中的常見錯誤。

一、邊的添加邏輯詳解

邊的插入操作 insert_vectex_into_graph 可分解為四個關鍵步驟：

1. 空圖判斷：若圖中無頂點，直接在 pGraph->head 建立首個頂點與邊
2. 起始頂點檢查：遍歷頂點鏈表尋找 start 頂點，不存在則建立新頂點並插入頭部
3. 邊重複性檢測：在目標頂點的鄰接鏈表中查找 end 邊，若已存在則返回失敗
4. 邊插入與計數更新：將新邊插入鄰接表頭部，並更新頂點邊計數 number 與圖總邊數 count

核心代碼實現

STATUS insert_vectex_into_graph(GRAPH* pGraph, int start, int end, int weight) {
    VECTEX* pVectex;
    LINE* pLine;

    if (NULL == pGraph) return FALSE;

    // 情況1：空圖直接建立首節點
    if (NULL == pGraph->head) {
        pGraph->head = create_new_vectex_for_graph(start, end, weight);
        pGraph->head->number++;
        pGraph->count++;
        return TRUE;
    }

    // 情況2：尋找或建立起始頂點
    pVectex = find_vectex_in_graph(pGraph->head, start);
    if (NULL == pVectex) {
        pVectex = create_new_vectex_for_graph(start, end, weight);
        pVectex->next = pGraph->head;
        pGraph->head = pVectex;
        pGraph->head->number++;
        pGraph->count++;
        return TRUE;
    }

    // 情況3：檢查邊是否已存在
    pLine = find_line_in_graph(pVectex->neighbor, end);
    if (NULL != pLine) return FALSE;  // 邊已存在

    // 情況4：插入新邊並更新計數
    pLine = create_new_line(end, weight);
    pLine->next = pVectex->neighbor;
    pVectex->neighbor = pLine;
    pVectex->number++;
    return TRUE;
}

二、邊的刪除策略：先建小工具，再組大功能

刪除操作的關鍵在於先實現通用的鏈表節點刪除函數，再在主刪除函數中調用：

1. 頂點刪除輔助函數

STATUS delete_old_vectex(VECTEX** ppVectex, int start) {
    VECTEX* pVectex = find_vectex_in_graph(*ppVectex, start);
    if (NULL == pVectex) return FALSE;

    // 處理頭節點刪除
    if (pVectex == *ppVectex) {
        *ppVectex = pVectex->next;
        free(pVectex);
        return TRUE;
    }

    // 尋找前驅節點並斷鏈
    VECTEX* prev = *ppVectex;
    while (pVectex != prev->next) prev = prev->next;
    prev->next = pVectex->next;
    free(pVectex);
    return TRUE;
}

2. 邊刪除輔助函數

STATUS delete_old_line(LINE** ppLine, int end) {
    LINE* pLine = find_line_in_graph(*ppLine, end);
    if (NULL == pLine) return FALSE;

    if (pLine == *ppLine) {
        *ppLine = pLine->next;
        free(pLine);
        return TRUE;
    }

    LINE* prev = *ppLine;
    while (pLine != prev->next) prev = prev->next;
    prev->next = pLine->next;
    free(pLine);
    return TRUE;
}

3. 主刪除邏輯：可逆操作的完美體現

STATUS delete_vectex_from_graph(GRAPH* pGraph, int start, int end, int weight) {
    VECTEX* pVectex;
    LINE* pLine;
    STATUS result;

    if (NULL == pGraph || NULL == pGraph->head) return FALSE;

    // 1. 尋找起始頂點
    pVectex = find_vectex_in_graph(pGraph->head, start);
    if (NULL == pVectex) return FALSE;

    // 2. 尋找目標邊
    pLine = find_line_in_graph(pVectex->neighbor, end);
    if (NULL == pLine) return FALSE;  // 注意：原代碼此處邏輯有誤，應為 NULL == pLine

    // 3. 刪除邊並更新計數
    result = delete_old_line(&pVectex->neighbor, end);
    assert(TRUE == result);
    pVectex->number--;

    // 4. 若頂點無邊則連帶刪除頂點
    if (0 == pVectex->number) {
        result = delete_old_vectex(&pGraph->head, start);
        assert(TRUE == result);
    }

    pGraph->count--;
    return TRUE;
}

三、工程實踐心得

• 函數拆解原則：單一函數不超過 50 行，複雜邏輯拆解為可復用的原子操作
• 防禦性編程：所有指針操作前必須檢查空指針，使用斷言驗證關鍵操作結果
• 測試驅動：每個小函數獨立測試，再進行集成測試，確保邊界條件正確處理

掌握這種「自底向上」的構建思維，不僅適用於圖算法，更是處理複雜指結構操作的通用方法論。