콘텐츠로 바로가기
HY_TECH_BASE

Graph Foundations & Flow

정점과 간선의 연결을 통해 현실 세계의 관계와 네트워크를 모델링하는 그래프 자료구조와, 최단 경로 및 네트워크 유량의 물리적 최적화를 다루는 학습 노드입니다.

sys.entry
M

Me

hyunyoun's Blog

posts6 min read

1. Overview

그래프 기초 및 유량(Graph Foundations & Flow, GFF)은 단순한 선형 구조를 넘어 전 지구적 네트워크와 유기적 관계를 수리적으로 설계하고 통제하는 시스템의 '연결 지능'입니다.

인터넷의 데이터 전송이나 도로망의 교통 흐름은 모두 이 자료구조 위에 지어집니다. 학습자는 정점(Node)과 간선(Edge)으로 이루어진 **그래프(Graph)**의 물리적 표현 방식인 인접 행렬과 인접 리스트를 배웁니다. 또한, 모든 정점을 빠짐없이 뒤지는 DFS/BFS 탐색과, 두 지점 사이의 가장 빠른 길을 찾는 최단 경로 알고리즘을 익힙니다. 특히 네트워크 상에서 흐를 수 있는 최대의 양을 계산하는 **최대 유량(Maximum Flow)**의 수리적 원리를 분석합니다. 이를 통해 복잡한 세계의 연결성을 물리적 자원 효율성으로 치환하여 정복하는 법을 확보합니다.

2. Scope & Boundaries

In-Scope

  • Graph Representations: Adjacency Matrix vs. Adjacency List의 공간/시간 물리적 효율 비교
  • Graph Traversals: DFS와 BFS의 실행 큐/스택 물리 및 탐색 순서 불변성
  • Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall 알고리즘의 수리적 설계
  • Network Flow: Ford-Fulkerson, Edmonds-Karp 알고리즘과 용량/흐름의 물리 제약

Out-of-Scope

  • 소셜 네트워크의 고차원 데이터 마이닝 알고리즘 (06-02-XX 데이터 분석 영역으로 위임)
  • 특정 지도 서비스의 상용 길 찾기 엔진 구현 상세

Boundaries

  • GFF vs. Trees: 트리가 '위계가 분명한 특수 그래프'라면, GFF는 '순환(Cycle)과 방향성'이 공존하는 일반화된 네트워크 물리에 집중하여 구분합니다.

3. Counterexample

  • 단순히 "점과 선을 잇는 것"이라 설명하는 것은 GFF 학습이 아닙니다. 정점 수(VV)가 적고 간선 수(EE)가 많은 완전 그래프(Dense graph)에서 왜 인접 리스트보다 인접 행렬이 물리적으로 더 효율적일 수 있는지 수리적으로 입증할 수 있어야 하며, 음수 가중치가 있는 그래프에서 왜 다익스트라 알고리즘이 물리적 오작동을 하는지 벨만-포드와의 차이점을 통해 분석하지 못한다면 GFF의 본질적인 제약 사항을 놓친 것입니다.

4. Prerequisites

  • Linked Lists & Pointer Logic (Basic): 인접 리스트 구현을 위한 연결 기반 이해가 필수입니다. (04-01-02 LPL)
  • Heaps & Priority Queues (Recommended): 다익스트라 가속을 위한 힙 이해가 권장됩니다. (04-02-02 HPQ)

5. Learning Map

  1. The Web of Nodes: 배열과 리스트를 넘어 정점들이 얽히고설키는 그래프의 물리 배치를 이해합니다.
  2. Infinite Search: 안개 속의 그물망을 규칙적으로 훑어나가는 DFS/BFS의 경로를 그립니다.
  3. The Shortest Line: 수천 개의 갈림길 속에서 최소 비용의 직선 거리(Path)를 계산합니다.
  4. Capacity Limits: 파이프가 터지지 않게 흐름(Flow)을 조율하는 최대 유량의 물리를 완성합니다.

6. Learning Topics

Basic

  • Why to Learn: 데이터를 단순히 담는 것을 넘어 '관계'를 수리적으로 정의하기 위해서입니다.
  • What to Learn:
    • Adjacency Matrix: 2차원 배열을 통한 직접적 연결 유무의 물리 사상
    • Adjacency List: 동적 리스트를 통한 희소(Sparse) 연결의 메모리 압축
    • Breadth-First Search (BFS): 큐를 이용해 파도처럼 층층이 퍼져나가는 물리 탐색
  • How to Learn:
    • 5개의 친구 관계 네트워크를 행렬과 리스트로 각각 그려보고, 메모리 사용량을 직접 산출 실습
    • BFS를 통해 최단 거리를 찾을 때 왜 '방문 여부(Visited)' 체크가 물리적 무한 루프를 막는지 증명
  • Implement: 인접 리스트를 기반으로 BFS와 DFS를 수행하여 방문 순서를 출력하는 기초 코드

Core: 가중치 그래프와 최단 경로 (Shortest Path Algorithms)

  • Why to Learn: 자원이 불균등한 환경(가중치)에서 최적의 이동 물리 경로를 찾기 위함입니다.
  • What to Learn:
    • Dijkstra's Algorithm: 현재 시점의 최소값을 우선순위 큐로 뽑아내는 최적화 물리
    • Bellman-Ford: 음수 간선이 있을 때 '완화(Relaxation)' 연산을 반복하며 해를 찾는 법
    • All-pairs Shortest Path: Floyd-Warshall의 거쳐가는 노드 중심 3중 루프 수리 논리
  • How to Learn:
    • 종이 지도의 도로마다 숫자를 적고, 다익스트라 테이블을 한 줄씩 갱신하며 수동 길 찾기 실습
    • 벨만-포드에서 V−1V-1번의 완화 후에도 값이 바뀌면 왜 '음수 사이클'이 존재하는지 물리적 유도
  • Implement: 우선순위 큐를 활용한 고성능 다익스트라 최단 경로 라이브러리

Practical

Core: 최소 신장 트리와 연결성 (Spanning Trees & Connectivity)

  • Why to Learn: 최소한의 비용으로 모든 지점을 연결하는 기간망 설계를 물리적으로 수행하기 위해서입니다.
  • What to Learn:
    • Kruskal's & Disjoint-set: 간선을 가중치 순으로 정렬하고 합집합 연산으로 사이클을 막는 물리
    • Prim's Integration: 시작 정점부터 하나씩 영토를 확장해나가는 탐욕적 물리 전개
    • SCC (Strongly Connected Components): 서로가 서로에게 도달할 수 있는 섬(Cluster)들을 발췌하는 기법
  • How to Learn:
    • 복잡한 유선망 예시에서 크루스칼 알고리즘을 적용하며 Union-Find 자료구조가 결합되는 과정 분석 실습
    • 단절점(Articulation Point)을 찾아 네트워크가 쪼개지는 물리적 취약 지점 파악 실습
  • Implement: Union-Find를 이용해 정점들을 하나의 그룹으로 묶고 분리하는 관리 클래스

Advanced

Core: 네트워크 유량과 매칭 (Network Flow & Matching)

  • Why to Learn: 한정된 통로(Pipe) 용량 내에서 전체 처리량(Throughput)을 극한으로 높이기 위함입니다.
  • What to Learn:
    • Capacity & Flow: 파이프의 두께(Capacity)와 현재 흐르는 양(Flow)의 물리적 상관관계
    • Residual Graph: 남은 용량을 역으로 추적하여 새로운 흐름을 찾는 잔여 그래프 물리학
    • Bipartite Matching: 지원자와 업무를 유량 문제로 치환하여 최대로 짝을 지어주는 방식
  • How to Learn:
    • 포드-풀커슨(Ford-Fulkerson) 수동 시뮬레이션을 통해 더 이상 갈 수 없을 때까지 흐름을 쥐어짜 내는 과정 실습
    • 에드몬드-카프(Edmonds-Karp)가 왜 BFS를 써서 물리적 종료를 보장하는지 수리적 분석
  • Implement: 에드몬드-카프 알고리즘을 이용한 소스-싱크 간 최대 유량 산출 엔진

7. Terminology

Term (EN / ko, abbr) 1문장 정의 단계(기본/권장/실무/심화) 역할/맥락 관련 개념 유사/대비/함께 사용 오해 포인트 Evidence(Primary/Secondary/Industry) Flags(core)
Graph 정점과 그들을 잇는 간선들의 집합으로 현실의 관계를 추상화한 자료구조입니다. 기본 관계 기초 Node / Edge Tree 반드시 모든 노드가 연결되진 않음 P1:CS2023 core
Adjacency List 각 정점에서 연결된 다른 정점들의 주소를 리스트로 관리하는 메모리 효율적 방식입니다. 기본 물리 표현 Memory / Pointer Matrix 데이터 검색 속도가 행렬보다 느림 P1:CS2023 core
Relaxation (완화) 새로운 경로를 발견했을 때 기존의 최단 거리 정보를 더 작은 값으로 갱신하는 수리 연산입니다. 추천 경로 갱신 Update / Path Smoothing 단순히 '값을 바꿈' 이상의 의미 P1:CS2023 core
Maximum Flow 네트워크의 모든 간선 용량 제약을 만족하며 소스에서 싱크로 보낼 수 있는 최대 물리 유량입니다. 심화 용량 최적화 Capacity / Sink Cut '최단 경로'와는 상충하는 개념 Industry core

8. References

Primary

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)'을 유량 문제로 설계하는 방안을 기술할 수 있는 가?

Concepts & Tags

#graph-theory#shortest-path#network-flow#adjacency-matrix#graph-traversal