[Daily morning study] 네트워크 플로우(최대 유량) - Ford-Fulkerson과 Edmonds-Karp

01 Nov 2026 in Daily morning study / DSA

#daily morning study

네트워크 플로우란?

네트워크 플로우(Network Flow)는 그래프에서 소스(source) 에서 싱크(sink) 까지 흘릴 수 있는 최대 유량(Maximum Flow)을 구하는 문제다.

각 간선에는 용량(capacity)이 있고, 흐르는 유량(flow)은 그 용량을 초과할 수 없다.

현실 세계 예시:

파이프망에서 물이 흐르는 최대 양
도로망에서 차량 최대 통행량
통신망에서 데이터 전송 최대 대역폭

기본 개념 정의

용량(Capacity)과 유량(Flow)

c(u, v) : 간선 u→v의 최대 용량
f(u, v) : 간선 u→v에 실제로 흐르는 유량

유량의 3가지 성질

성질	설명
용량 제한	`f(u, v) ≤ c(u, v)` — 유량은 용량을 초과할 수 없음
유량 보존	소스/싱크 제외 모든 노드에서 들어오는 유량 = 나가는 유량
반대 방향	`f(u, v) = -f(v, u)` — 반대 간선의 유량은 음수

잔여 그래프(Residual Graph)

잔여 그래프는 더 유량을 보낼 수 있는 여유를 나타낸다.

정방향 잔여 용량: r(u, v) = c(u, v) - f(u, v)
역방향 잔여 용량: r(v, u) = f(u, v) (이미 보낸 유량을 취소할 수 있음)

역방향 간선을 두는 이유: 한번 보낸 유량을 다시 회수(취소)하는 경로를 허용해서 더 최적의 해를 찾기 위함이다.

Ford-Fulkerson 알고리즘

핵심 아이디어

증가 경로(Augmenting Path) — 소스에서 싱크까지 잔여 용량이 남은 경로 — 를 반복해서 찾아 유량을 보내는 방식이다.

1. 모든 유량을 0으로 초기화
2. while (소스 → 싱크로 가는 증가 경로가 존재):
   a. 경로상의 최소 잔여 용량 bottleneck 계산
   b. 경로의 각 간선에 bottleneck만큼 유량 추가
   c. 역방향 간선에서 bottleneck만큼 차감
3. 최대 유량 반환

Python 구현 (DFS 기반)

from collections import defaultdict

def dfs(graph, source, sink, visited, flow):
    if source == sink:
        return flow
    visited.add(source)
    for next_node, capacity in graph[source].items():
        if next_node not in visited and capacity > 0:
            bottleneck = dfs(graph, next_node, sink, visited, min(flow, capacity))
            if bottleneck > 0:
                graph[source][next_node] -= bottleneck
                graph[next_node][source] += bottleneck
                return bottleneck
    return 0

def ford_fulkerson(graph, source, sink):
    max_flow = 0
    while True:
        bottleneck = dfs(graph, source, sink, set(), float('inf'))
        if bottleneck == 0:
            break
        max_flow += bottleneck
    return max_flow

# 그래프 구성 예시
graph = defaultdict(lambda: defaultdict(int))
# u → v, 용량 c 추가
def add_edge(graph, u, v, c):
    graph[u][v] += c
    graph[v][u] += 0  # 역방향 초기화 (이미 0이지만 명시)

add_edge(graph, 'S', 'A', 10)
add_edge(graph, 'S', 'B', 10)
add_edge(graph, 'A', 'T', 10)
add_edge(graph, 'B', 'T', 10)
add_edge(graph, 'A', 'B', 2)

print(ford_fulkerson(graph, 'S', 'T'))  # 20

시간 복잡도

O(E × f) — E는 간선 수, f는 최대 유량
유량 값이 매우 크거나 간선 용량이 무리수이면 무한 루프에 빠질 수 있음
실제로 DFS 기반 Ford-Fulkerson은 정수 용량에만 안전하게 쓸 수 있음

Edmonds-Karp 알고리즘

Ford-Fulkerson에서 증가 경로를 DFS가 아닌 BFS 로 찾는 방식이다. 항상 최단 경로(간선 수 기준)를 선택하기 때문에 시간 복잡도가 개선된다.

왜 BFS가 더 나은가?

DFS는 경우에 따라 매우 비효율적인 경로를 선택해 같은 유량을 조금씩만 증가시킬 수 있다. BFS로 최단 경로를 선택하면 증가 경로의 길이가 단조 증가함이 보장되어 알고리즘이 빠르게 수렴한다.

Python 구현 (BFS 기반)

from collections import defaultdict, deque

def bfs(capacity, source, sink, parent):
    visited = {source}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in capacity[u]:
            if v not in visited and capacity[u][v] > 0:
                visited.add(v)
                parent[v] = u
                if v == sink:
                    return True
                queue.append(v)
    return False

def edmonds_karp(capacity, source, sink):
    max_flow = 0
    while True:
        parent = {}
        if not bfs(capacity, source, sink, parent):
            break
        # 경로상의 최소 잔여 용량 계산
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, capacity[u][v])
            v = u
        # 유량 갱신
        v = sink
        while v != source:
            u = parent[v]
            capacity[u][v] -= path_flow
            capacity[v][u] += path_flow
            v = u
        max_flow += path_flow
    return max_flow

# 인접 행렬 방식 그래프 (노드 수가 적을 때)
n = 6  # 노드 수
cap = defaultdict(lambda: defaultdict(int))

# S=0, T=5
cap[0][1] = 16; cap[0][2] = 13
cap[1][2] = 10; cap[1][3] = 12
cap[2][1] = 4;  cap[2][4] = 14
cap[3][2] = 9;  cap[3][5] = 20
cap[4][3] = 7;  cap[4][5] = 4

print(edmonds_karp(cap, 0, 5))  # 23

시간 복잡도

O(V × E²) — V는 정점 수, E는 간선 수
최대 유량 크기와 무관하므로 Ford-Fulkerson보다 안정적
실제 대부분의 경쟁 프로그래밍 문제에서 이 복잡도로 충분

최대 유량 = 최소 컷 (Max-Flow Min-Cut 정리)

네트워크 플로우에서 가장 중요한 정리다.

네트워크의 최대 유량 = 소스와 싱크를 분리하는 최소 컷의 용량

컷(Cut) 이란 소스 쪽 집합 S와 싱크 쪽 집합 T로 그래프의 모든 노드를 나누었을 때, S→T로 가는 간선들의 집합이다.

최소 컷을 찾는 방법:

최대 유량 계산 후 잔여 그래프 구성
잔여 그래프에서 소스로부터 도달 가능한 노드 집합 = S
도달 불가능한 노드 집합 = T
S→T 방향의 원본 간선들이 최소 컷

실전 활용 예시

이분 매칭(Bipartite Matching)

이분 그래프에서 최대 매칭도 네트워크 플로우로 해결할 수 있다.

소스 → 왼쪽 집합 각 노드 (용량 1)
왼쪽 → 오른쪽 (조건 간선, 용량 1)
오른쪽 집합 각 노드 → 싱크 (용량 1)

최대 유량 = 최대 매칭 수

프로젝트 선택 문제

이익을 최대화하면서 비용 제약을 만족하는 프로젝트 선택 — 최소 컷으로 모델링한다.

알고리즘 비교 요약

항목	Ford-Fulkerson (DFS)	Edmonds-Karp (BFS)
경로 탐색	DFS	BFS
시간 복잡도	O(E × f)	O(V × E²)
유량 크기 의존	있음 (큰 f면 느림)	없음
무리수 용량	무한 루프 위험	안전
사용 추천	작은 f, 간단한 구현	일반적인 경우

핵심 정리

Ford-Fulkerson: 증가 경로를 반복 탐색해 유량 보내기, DFS 기반
Edmonds-Karp: BFS로 최단 증가 경로 선택, 시간 복잡도 O(VE²)로 안정적
잔여 그래프의 역방향 간선이 핵심 — 이전 결정을 되돌릴 수 있게 함
Max-Flow Min-Cut 정리: 최대 유량 = 최소 컷 용량
이분 매칭 등 다양한 문제를 플로우로 변환해 풀 수 있음

[Daily morning study] 네트워크 플로우(최대 유량) - Ford-Fulkerson과 Edmonds-Karp

네트워크 플로우란?

기본 개념 정의

용량(Capacity)과 유량(Flow)

유량의 3가지 성질

잔여 그래프(Residual Graph)

Ford-Fulkerson 알고리즘

핵심 아이디어

Python 구현 (DFS 기반)

시간 복잡도

Edmonds-Karp 알고리즘

왜 BFS가 더 나은가?

Python 구현 (BFS 기반)

시간 복잡도

최대 유량 = 최소 컷 (Max-Flow Min-Cut 정리)

실전 활용 예시

이분 매칭(Bipartite Matching)

프로젝트 선택 문제

알고리즘 비교 요약

핵심 정리

🐒🇰🇷

Error

네트워크 플로우란?

기본 개념 정의

용량(Capacity)과 유량(Flow)

유량의 3가지 성질

잔여 그래프(Residual Graph)

Ford-Fulkerson 알고리즘

핵심 아이디어

Python 구현 (DFS 기반)

시간 복잡도

Edmonds-Karp 알고리즘

왜 BFS가 더 나은가?

Python 구현 (BFS 기반)

시간 복잡도

최대 유량 = 최소 컷 (Max-Flow Min-Cut 정리)

실전 활용 예시

이분 매칭(Bipartite Matching)

프로젝트 선택 문제

알고리즘 비교 요약

핵심 정리

Templates (for web app):

Error