C語言課程設計：用圖論解決分油問題（鄰接矩陣求最短路徑）

問題背景

經典的「分油問題」（又稱水壺問題）是圖論在程式設計教學中的常見案例。給定三個容量不同的油瓶與一個目標容量，需透過倒油操作達到目標狀態。本質上是一個狀態空間搜尋問題，每個狀態代表三瓶油的當前體積，合法的倒油動作構成狀態間的邊。

核心思路：建模為圖的最短路徑

1. 狀態定義：用三元組 (a, b, c) 表示三瓶油當前體積，初始狀態通常為 (大瓶滿, 0, 0)。
2. 狀態轉移：任選兩瓶 (從瓶 i 倒向瓶 j)，倒油量為 min(瓶i當前量, 瓶j剩餘容量)。每次操作產生新狀態。
3. 圖的建構：將所有可達狀態作為節點，合法操作作為邊。因邊權皆為 1（每步操作代價相同），可用廣度優先搜尋（BFS）尋找最短路徑。
4. 鄰接矩陣實現：雖然鄰接矩陣直觀，但狀態數可能達數萬（如容量上限 1000 時狀態數 ~10^6），矩陣極其稀疏且佔用記憶體大。實務上強烈建議改用鄰接表 + BFS或直接在 BFS 中動態生成鄰接狀態，無需顯式儲存整張圖。

關鍵程式碼片段（BFS 核心邏輯）

// 狀態結構
typedef struct {
    int v[3]; // 三瓶油體積
    int prev; // 前驅節點索引，用於回溯路徑
    int action; // 記錄操作：從哪倒向哪
} State;

State states[MAX_STATES];
bool visited[MAX_CAP+1][MAX_CAP+1][MAX_CAP+1]; // 三維訪問標記

// BFS 主循環
while (front < rear) {
    State cur = q[front++];
    if (is_target(cur)) { /* 找到目標，回溯輸出路徑 */ break; }
    
    // 枚舉 6 種倒油方向 (3*2)
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) if (i != j) {
            State nxt = pour(cur, i, j); // 執行倒油
            if (!visited[nxt.v[0]][nxt.v[1]][nxt.v[2]]) {
                visited[...] = true;
                nxt.prev = front - 1;
                q[rear++] = nxt;
            }
        }
    }
}

常見坑點與優化

• 狀態去重：務必使用三維陣列或雜湊表記錄訪問過的狀態，否則會陷入無限迴圈。
• 路徑回溯：利用 `prev` 欄位從目標節點倒推回初始狀態，再反轉輸出。
• 不可達判斷：若隊列耗盡仍未達目標，說明無解（通常因總油量不夠或目標非最大公約數倍數）。

總結

分油問題是圖論建模與 BFS 算法的優秀練習。雖然題目要求「鄰接矩陣」，但實際工程中應根據資料規模選擇鄰接表或隱式圖搜尋。掌握狀態壓縮、訪問標記、路徑回溯三大核心技巧，即可輕鬆解決此類狀態空間搜尋問題。