หา Minimum s-t Cut ใน Flow Network ด้วย C++

ใน Flow Network, s-t cut คือการตัดที่แยก source (s) และ sink (t) ออกเป็น subset ต่างกัน ประกอบด้วยขอบ (edges) ที่ไปจาก source side ไป sink side ความจุ (capacity) ของ cut = ผลรวมความจุขอบใน cut-set ภารกิจคือหา minimum capacity s-t cut และแสดงขอบทั้งหมดของ cut นั้น

ตัวอย่าง

กราฟ 6 โหนด (ภาพ) → Output: [(1,3), (4,3), (4,5)]

อัลกอริทึม (Ford-Fulkerson / Edmonds-Karp + Min Cut)

1. ใช้ BFS หา Augmenting Path ใน Residual Graph (Edmonds-Karp)
2. อัปเดต Residual Capacity ตาม path flow
3. ทำซ้ำจนไม่มี augmenting path → ได้ Max Flow
4. จาก Residual Graph สุดท้าย ใช้ DFS จาก source หาโหนดที่เข้าถึงได้ (set S)
5. ขอบที่จาก S ไป V\S ในกราฟต้นฉบับ = Minimum Cut

โค้ดตัวอย่าง (C++)

#include <bits/stdc++.h>
using namespace std;

#define NODES 6

int bfs(int graph[NODES][NODES], int src, int sink, int par[]) {
    bool vis[NODES];
    memset(vis, 0, sizeof(vis));
    queue<int> que;
    que.push(src);
    vis[src] = true;
    par[src] = -1;
    
    while (!que.empty()) {
        int u1 = que.front(); que.pop();
        for (int v1 = 0; v1 < NODES; v1++) {
            if (!vis[v1] && graph[u1][v1] > 0) {
                que.push(v1);
                par[v1] = u1;
                vis[v1] = true;
            }
        }
    }
    return (vis[sink] == true);
}

void dfs(int graph[NODES][NODES], int src, bool vis[]) {
    vis[src] = true;
    for (int i = 0; i < NODES; i++)
        if (graph[src][i] && !vis[i])
            dfs(graph, i, vis);
}

void minCut(int graph[NODES][NODES], int src, int sink) {
    int temp_graph[NODES][NODES];
    for (int u = 0; u < NODES; u++)
        for (int v = 0; v < NODES; v++)
            temp_graph[u][v] = graph[u][v];
    
    int par[NODES];
    while (bfs(temp_graph, src, sink, par)) {
        int path_flow = INT_MAX;
        for (int v = sink; v != src; v = par[v]) {
            int u = par[v];
            path_flow = min(path_flow, temp_graph[u][v]);
        }
        for (int v = sink; v != src; v = par[v]) {
            int u = par[v];
            temp_graph[u][v] -= path_flow;
            temp_graph[v][u] += path_flow;
        }
    }
    
    bool vis[NODES];
    memset(vis, false, sizeof(vis));
    dfs(temp_graph, src, vis);
    
    for (int i = 0; i < NODES; i++)
        for (int j = 0; j < NODES; j++)
            if (vis[i] && !vis[j] && graph[i][j])
                cout << "(" << i << ", " << j << ")" << endl;
}

int main() {
    int graph1[NODES][NODES] = {
        {0, 17, 14, 0, 0, 0},
        {0, 0, 11, 13, 0, 0},
        {0, 5, 0, 0, 15, 0},
        {0, 0, 9, 0, 0, 21},
        {0, 0, 0, 8, 0, 5},
        {0, 0, 0, 0, 0, 0}
    };
    minCut(graph1, 0, 5);
}

ผลลัพธ์

(1, 3)
(4, 3)
(4, 5)

ทฤษฎีสำคัญ: Max-Flow Min-Cut Theorem ระบุว่า Maximum Flow จาก s ถึง t เท่ากับ Capacity ของ Minimum s-t Cut