Belajar Algoritm - Network Flow (Pengenalan)

#Pendahuluan

Setelah di episode 19-20 kita membahas shortest path dan MST, pada episode ini kita menutup FASE 5: GRAPH ALGORITHMS dengan Network Flow — salah satu topik paling powerful di graph theory. Network flow menyelesaikan banyak masalah yang tampak tidak berhubungan: matching, assignment, project selection, dan sirkulasi dengan demand.

Max-flow min-cut theorem menghubungkan dua konsep yang tampak berbeda — mengalirkan data maksimum dari source ke sink sama dengan menemukan pemotongan minimum yang memisahkan source dari sink. Hubungan ini mengejutkan dan sangat berguna.

#Konsep Dasar

#Flow Network

Flow network adalah graph berarah berbobot di mana:

Setiap edge (u, v) memiliki capacity c(u, v) — jumlah maksimum yang bisa mengalir.
Setiap edge memiliki flow f(u, v) — jumlah yang benar-benar mengalir.
Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v).
Flow conservation: untuk setiap vertex (kecuali source/sink), total flow masuk = total flow keluar.

#Source dan Sink

Source (s): vertex yang hanya menghasilkan flow (tidak ada flow masuk).
Sink (t): vertex yang hanya menyerap flow (tidak ada flow keluar).

#Max-Flow Min-Cut Theorem

Teorema fundamental: maximum flow dari source ke sink = minimum cut yang memisahkan source dari sink.

Cut adalah partition vertex menjadi dua set: S (berisi source) dan T (berisi sink). Capacity cut = total capacity edge dari S ke T.

Artinya: untuk menemukan bottleneck sistem, kalian bisa menghitung flow maksimum ATAU mencari pemotongan minimum — hasilnya sama.

#Edmonds-Karp Algorithm

Edmonds-Karp adalah implementasi Ford-Fulkerson yang menggunakan BFS untuk mencari augmenting path (jalur dari source ke sink di residual graph). Ford-Fulkerson secara iteratif menambah flow melalui augmenting path sampai tidak ada lagi.

python

from collections import deque
 
def edmonds_karp(capacity, source, sink, n):
    """capacity[n][n] = matriks kapasitas"""
    flow = [[0] * n for _ in range(n)]
    total_flow = 0
    
    while True:
        # BFS cari augmenting path
        parent = [-1] * n
        parent[source] = source
        queue = deque([source])
        
        while queue:
            u = queue.popleft()
            for v in range(n):
                if parent[v] == -1 and capacity[u][v] - flow[u][v] > 0:
                    parent[v] = u
                    queue.append(v)
        
        if parent[sink] == -1:
            break  # tidak ada augmenting path
        
        # Cari bottleneck capacity
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, capacity[u][v] - flow[u][v])
            v = u
        
        # Update flow di sepanjang path
        v = sink
        while v != source:
            u = parent[v]
            flow[u][v] += path_flow
            flow[v][u] -= path_flow  # flow balik
            v = u
        
        total_flow += path_flow
    
    return total_flow

#Kompleksitas

Metrik	Nilai
Time	O(VE²) — Edmonds-Karp (BFS)
Space	O(V²) — matriks kapasitas
Augmenting paths	O(VE) — setiap BFS menambah minimal 1 unit capacity

Note

Ford-Fulkerson menggunakan DFS (O(E × max_flow)), yang bisa lambat untuk flow besar. Edmonds-Karp menggunakan BFS → O(VE²) — tidak bergantung pada nilai capacity. Untuk graph besar, gunakan Dinic's algorithm (O(V²E)) atau Push-relabel (O(V³)).

#Aplikasi Network Flow

#Bipartite Matching

Masalah: pasangkan worker ke task — setiap worker hanya bisa mengerjakan satu task, setiap task hanya dikerjakan satu worker.

Transformasi: buat graph flow dari source → worker (capacity 1), worker → task (capacity 1), task → sink (capacity 1). Max flow = maximum matching.

#Project Selection

Pilih proyek yang menghasilkan profit. Setiap proyek memiliki biaya dan dependensi ke proyek lain. Transformasi ke max-flow: source → proyek (profit), proyek → sink (biaya), dependensi → edge capacity infinite. Proyek yang tidak dipotong dari source = proyek yang dipilih.

Tip

Kunci menggunakan network flow: identifikasi apa yang mengalir (worker, data, uang) dan apa yang membatasi (capacity, biaya, ketersediaan). Jika masalah bisa dimodelkan sebagai flow dengan constraints → gunakan max-flow.

#Penutup

Pada episode 21 ini, kalian telah memahami:

Flow network: graph berarah berbought dengan capacity dan flow conservation.
Max-flow min-cut theorem: flow maksimum = cut minimum — dua sisi koin yang sama.
Edmonds-Karp: BFS-based Ford-Fulkerson, O(VE²), tidak bergantung pada capacity.
Aplikasi: bipartite matching, project selection, sirkulasi dengan demand.

Ini menutup FASE 5: GRAPH ALGORITHMS. Di episode 22 selanjutnya kita masuk ke FASE 6: APPLIED, RANDOMIZED & MODERN — membahas String Algorithms: KMP, Rabin-Karp, dan Z-algorithm untuk pattern matching efisien. Sampai jumpa di episode 22!