Graph Foundations & Flow

1. Overview

그래프 기초와 흐름(Graph Foundations & Flow)은 도시 간 도로망부터 소셜 네트워크, 인터넷 라우팅, 회로 설계, 의존성 그래프까지 현실의 관계 구조를 정점(Vertex)과 간선(Edge)으로 추상화하여 탐색·최단경로·최대흐름·매칭을 수학으로 지배하는 알고리즘의 왕국입니다.

학습자는 그래프의 두 가지 표현(인접 행렬 vs 인접 리스트)의 메모리·시간 트레이드오프를 뜯어봅니다. BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 탐색 순서와 응용(위상 정렬, SCC)을 해부하고, 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall) 세 가지 최단 경로 알고리즘의 가정(음수 간선 허용 여부, 단일·전쌍 최단 경로)을 비교합니다. 마지막으로 최대 흐름(Max-Flow, Ford-Fulkerson), 최소 컷-최대 흐름 정리(Max-Flow Min-Cut Theorem), **이분 매칭(Bipartite Matching)**을 해부하여 네트워크 용량 최적화 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 그래프 표현 (Graph Representation): 인접 행렬(Adjacency Matrix, O(V²)), 인접 리스트(Adjacency List, O(V+E)), 간선 리스트(Edge List).
• 그래프 탐색 (Graph Traversal): BFS(Queue 기반, 최단 홉), DFS(Stack/재귀, 위상 정렬, SCC Kosaraju/Tarjan).
• 최단 경로 (Shortest Path): Dijkstra(비음수 가중치, O((V+E)log V)), Bellman-Ford(음수 가중치, O(VE), 음수 사이클 탐지), Floyd-Warshall(전쌍, O(V³)).
• 최대 흐름 (Max-Flow): Ford-Fulkerson(증가 경로), Edmonds-Karp(BFS 증가 경로, O(VE²)), 이분 매칭(Bipartite Matching).

Out-of-Scope

• MST(최소 신장 트리): Kruskal/Prim → 04-03-03. Greedy Algorithms 영역.
• NP-하드 그래프 문제: Hamilton Cycle, Graph Coloring 최적화 → 04-03-04. Backtracking / 04-04-04. Complexity 영역.

Boundaries

• Dijkstra vs Bellman-Ford: Dijkstra는 음수 간선이 없는 그래프에서 O((V+E)log V)로 빠르지만, 음수 간선이 있으면 잘못된 답을 냅니다. Bellman-Ford는 음수 간선을 처리하고 음수 사이클을 탐지할 수 있지만 O(VE)로 느립니다. 간선 가중치가 모두 비음수이면 Dijkstra, 음수가 있으면 Bellman-Ford를 선택합니다.

3. Counterexample

• 방향 그래프 위상 정렬에 사이클 존재 (Topological Sort with Cycle): 의존성 그래프에서 A → B → C → A 순환 의존(Circular Dependency)이 있는데 DFS 위상 정렬을 수행하는 실수. 사이클이 있는 방향 그래프(Directed Graph)는 위상 정렬이 불가능합니다. DFS 중 회색(현재 탐색 중) 노드를 재방문하면 사이클 존재를 탐지하고 예외를 던져야 합니다. npm/pip 패키지 의존성 설치 시 이 오류로 순환 의존성 에러가 발생합니다.
• 음수 간선에서 다익스트라의 오답 (Dijkstra with Negative Edges): 그래프 A→B=5, A→C=1, C→B=-10에서 다익스트라로 A→B의 최단 거리를 구하는 경우. 다익스트라는 B=5를 확정(Finalize)한 뒤 나중에 A→C→B=-9를 발견해도 이미 확정된 B를 갱신하지 않습니다. 결과적으로 최단 거리 5(오답)를 반환합니다. 올바른 답은 -9이며 Bellman-Ford로만 구할 수 있습니다.

4. Prerequisites

• 재귀와 큐/스택 (Basic): DFS(재귀/스택), BFS(큐) 기반이므로 해당 자료구조가 필요합니다. (04-01-03 Stacks & Queues)
• 힙/우선순위 큐 (Recommended): Dijkstra의 핵심 자료구조. (04-02-02 Heaps)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 정점과 간선의 언어와 두 가지 탐색, 그래프 기초 (Graph Basics & BFS/DFS)

• Why to Learn: SNS 친구 관계(무방향 그래프), 패키지 의존성(방향 그래프 DAG), 지하철 노선도(가중치 그래프) 등 모든 관계 구조를 그래프로 모델링하고, BFS/DFS로 탐색하는 만능 도구를 장착하기 위함입니다.
• What to Learn:
  • Concepts: 방향/무방향/가중치 그래프, 인접 행렬(O(V²) 공간) vs 인접 리스트(O(V+E)), BFS(Queue, 최단 홉), DFS(Stack/재귀, 위상 정렬).
  • Skills: 위상 정렬(Kahn's BFS 방식 + DFS 방식), 사이클 탐지, SCC(강연결 요소).
  • Trade-offs: 인접 행렬은 O(1) 간선 존재 확인이 장점이지만 O(V²) 공간을 차지해 V=100만이면 10^12바이트(1TB)가 필요합니다. 인접 리스트는 O(V+E) 공간으로 희소 그래프에 적합하지만 특정 간선 존재 확인이 O(degree) 시간이 걸리는 트레이드오프.
• How to Learn:
  • 1단계: BFS 미로 탐색. 시작 정점을 큐에 넣고, 레벨별로 인접 미방문 정점을 큐에 추가. 처음 목적지를 꺼내는 순간이 최단 경로(최소 홉)를 찾은 것임을 해부합니다.
  • 2단계: DFS 위상 정렬. DFS 완료(Post-order) 순서의 역순이 위상 정렬 순서임을 증명. 과목 의존성 그래프에서 수강 순서 도출을 뜯어봅니다.
• Implement: 파이썬 Graph 클래스(인접 리스트). bfs(start, end) 최단 홉 경로 반환. topological_sort() DFS/Kahn's 두 방식. 과목 의존성 {'A':[], 'B':['A'], 'C':['A','B'], 'D':['C']} → 위상 정렬 ['A','B','C','D'] 검증.

Recommended

Core Topic 02: 음수 없는 그래프의 왕과 음수 허용의 보험, 최단 경로 알고리즘 (Dijkstra & Bellman-Ford)

• Why to Learn: 구글 지도 최단 경로(Dijkstra), 금융 차익 거래(Negative Cycle = Bellman-Ford), BGP 라우팅 프로토콜의 공통 핵심 알고리즘들을 조건에 따라 정확히 선택하는 역량을 갖추기 위함입니다.
• What to Learn:
  • Concepts: Dijkstra(탐욕적 선택, 비음수 간선 조건), Bellman-Ford(완화(Relax) V-1회 반복, 음수 사이클 탐지), SPFA(Bellman-Ford 큐 최적화).
  • Skills: Dijkstra Lazy Deletion, Bellman-Ford 음수 사이클 판별(V번째 완화 성공 시).
• How to Learn:
  • 1단계: Dijkstra의 완화(Relax) 단계: if dist[u] + w(u,v) < dist[v]: dist[v] = dist[u] + w(u,v). Min-Heap에서 최소 거리 정점을 꺼내 모든 인접 정점 완화. 방문 확정된 정점은 재방문 불필요(비음수 보장 덕분)를 해부합니다.
  • 2단계: Bellman-Ford: 모든 간선에 대해 완화를 V-1번 반복. V번째에도 완화가 성공하면 음수 사이클 존재. 금융 차익 거래 탐지(통화 환율 그래프에서 음수 사이클)에 적용하는 역학을 뜯어봅니다.
• Implement: dijkstra(graph, start) + bellman_ford(edges, V, start). 동일 그래프에 두 알고리즘 적용하여 동일 결과 assert. 음수 간선 추가 시 Dijkstra 오답, Bellman-Ford 정답 비교 데모. 음수 사이클 그래프에서 Bellman-Ford 탐지 로그.

Practical

Core Topic 03: 모든 쌍의 거리와 DAG 최적 경로, Floyd-Warshall과 DAG DP (Floyd-Warshall & DAG)

• Why to Learn: V개의 모든 정점 쌍 최단 경로(All-Pairs Shortest Path)를 O(V³) 단 3중 루프로 해결하는 Floyd-Warshall의 우아한 DP와, 프로젝트 일정 최장 경로(Critical Path Method)를 DAG DP로 구하는 역량을 장악하기 위함입니다.
• What to Learn:
  • Concepts: Floyd-Warshall dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j]), 거리 행렬 초기화, 음수 사이클 탐지(dp[i][i]<0).
  • Skills: DAG 최장 경로(프로젝트 임계 경로 CPM), 위상 정렬 순으로 완화.
• How to Learn:
  • 1단계: Floyd-Warshall: "정점 k를 경유해도 되는가?"를 k=0부터 V-1까지 순차 허용하며 dist[i][j]를 업데이트. k번째 반복 후 dist[i][j]는 "0~k번 정점만 경유 가능할 때 i→j 최단 거리"를 뜯어봅니다.
  • 2단계: DAG 최장 경로(Critical Path): 위상 정렬 순으로 정점을 처리하며 longest[v] = max(longest[u] + w(u,v)) 완화. 소프트웨어 개발 작업 의존성에서 임계 경로(병목 작업 체인) 탐색을 해부합니다.
• Implement: floyd_warshall(adj_matrix). 5개 정점 그래프에서 전쌍 거리 행렬 출력. 대각선 음수 값으로 음수 사이클 탐지 검증. dag_longest_path(graph, source) 구현으로 CPM 예시(작업 7개, 의존성 12개) 임계 경로 출력.

Advanced

Core Topic 04: 파이프의 최대 물 흐름과 최소 컷, 최대 흐름 (Max-Flow & Min-Cut)

• Why to Learn: 데이터센터 네트워크 최대 대역폭, 이미지 세그멘테이션, 인력 배치(이분 매칭)의 공통 수학 엔진인 Max-Flow와, 최소 비용으로 네트워크를 단절하는 Min-Cut의 동치 관계를 장악하기 위해서입니다.
• What to Learn:
  • Concepts: 소스(Source)/싱크(Sink), 용량(Capacity)/흐름(Flow), 잔여 그래프(Residual Graph), 증가 경로(Augmenting Path), Max-Flow Min-Cut Theorem.
  • Skills: Edmonds-Karp(BFS로 증가 경로, O(VE²)), 이분 매칭(Bipartite Matching = Max-Flow 특수 케이스).
• How to Learn:
  • 1단계: Ford-Fulkerson: 소스에서 싱크로의 경로를 찾아 최소 용량(Bottleneck) 만큼 흐름 증가. 잔여 그래프에 역방향 간선 추가. 더 이상 증가 경로가 없을 때까지 반복. 총 흐름 = 최대 흐름을 해부합니다.
  • 2단계: 이분 매칭: 왼쪽 그룹(지원자)과 오른쪽 그룹(직무) 사이 간선을 가진 이분 그래프(Bipartite Graph). 소스→모든 왼쪽(용량1), 모든 오른쪽→싱크(용량1), 이분 간선(용량1)으로 구성. Max-Flow = 최대 매칭 수를 뜯어봅니다.
• Implement: max_flow_edmonds_karp(graph, source, sink). BFS로 증가 경로 탐색, 잔여 그래프 업데이트. 5×5 이분 그래프 매칭(지원자 5명, 직무 5명)에 Max-Flow 적용하여 최대 매칭 수와 실제 매칭 쌍 출력. Min-Cut을 최대 흐름 계산 후 BFS로 도달 가능 정점 집합으로 구하는 구현.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Graph Data) — Graph context.
• [P1] CS2023 - AL/Algorithms and Complexity (Basic Graph Algorithms) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — Comprehensive graph and flow analysis.
• [Algorithms in C++, Part 5: Graph Algorithms] Sedgewick — Practical graph implementation.

Industry

• [Neo4j: Graph Data Modeling Standards] — Real-world graph database application.
• [Google: Pregel - A System for Large-Scale Graph Processing] — Distributed graph industry case.

9. Final Checklist

Primary

• '인접 행렬'과 '인접 리스트' 중 간선이 매우 적은 '희소 그래프'에 어느 것이 물리적으로 유리한지 설명 가능한가? (P1)
• 'BFS'가 가중치가 없는 그래프에서 왜 항상 '최단 경로'를 보장하는지 수리적으로 입증할 수 있는 가? (P1)

Secondary

• 다익스트라 알고리즘이 '음수 가중치'를 만났을 때, 왜 가중치를 더할수록 거리가 짧아지는 물리적 모순에 빠지는지 소통 가능한가?
• 그래프의 '최대 유량(Max Flow)'과 '최소 컷(Min Cut)'이 왜 수리적으로 동일한 물리적 의미를 갖는지 도출할 수 있는 가?

Industry

• 대규모 마이크로서비스 아키텍처(MSA)에서 서비스 간의 의존성을 그래프로 모델링하고, '순환 의존성'을 감지하는 방안을 제안할 수 있는 가? (SFIA)
• 클라우드 오케스트레이션 설계 시, 리소스 할당 최적화를 위해 '이분 매칭(Bipartite Matching)'을 유량 문제로 설계하는 방안을 기술할 수 있는 가?