weighted graph와 directed graph란 무엇이며, 어떤 문제를 모델링하나요?

Question

Accepted Answer

**directed graph(방향 그래프, 다이그래프)**에서는 간선에 **방향**이 있습니다(`A → B` ≠ `B → A`). **weighted graph(가중 그래프)**에서는 각 간선이 **수치적 비용**(거리, 시간, 용량)을 담습니다. 둘을 결합하면 관계가 단방향이고 비용을 갖는 실제 시스템을 모델링합니다.

## 표현

```text
Weighted directed graph:
  A --5--> B
  A --2--> C
  C --1--> B
가중치를 가진 Adjacency list:
  A: [(B,5), (C,2)]
  B: []
  C: [(B,1)]
```

```python
graph = {
    'A': [('B', 5), ('C', 2)],   # 방향 있는, 가중 간선
    'B': [],
    'C': [('B', 1)],
}
# 최단 A->B는 A->C->B = 2 + 1 = 3, 직접 간선 5가 아님.
```

## 무엇을 모델링하는가

| 분야 | 정점 | 가중 방향 간선 |
|---|---|---|
| 지도 / GPS | 교차로 | 일방통행 도로 + 이동 시간 |
| 네트워크 | 라우터 | 링크 + 지연/대역폭 |
| 작업 스케줄링 | 작업 | 의존성 + 소요 시간 |
| 금융 | 통화 | 환율 |

## 핵심 알고리즘

| 목표 | 알고리즘 | 복잡도 |
|---|---|---|
| 최단 경로(음이 아닌 가중치) | Dijkstra | O((V+E) log V) |
| 최단 경로(음수 간선) | Bellman-Ford | O(VE) |
| 의존성을 가진 순서 정하기 | 위상 정렬(Topological sort) | O(V+E) |
| 사이클 탐지 / 도달 가능성 | DFS | O(V+E) |

## 왜 중요한가

방향과 가중치는 추상적 그래프를, 실제 애플리케이션을 구동하는 라우팅, 스케줄링, 의존성 문제의 충실한 모델로 바꿉니다.

알고리즘 선택은 이 속성들에 달려 있습니다. 예를 들어 음수 가중치는 Dijkstra를 배제하고 Bellman-Ford를 요구합니다.

분야	정점	가중 방향 간선
지도 / GPS	교차로	일방통행 도로 + 이동 시간
네트워크	라우터	링크 + 지연/대역폭
작업 스케줄링	작업	의존성 + 소요 시간
금융	통화	환율

목표	알고리즘	복잡도
최단 경로(음이 아닌 가중치)	Dijkstra	O((V+E) log V)
최단 경로(음수 간선)	Bellman-Ford	O(VE)
의존성을 가진 순서 정하기	위상 정렬(Topological sort)	O(V+E)
사이클 탐지 / 도달 가능성	DFS	O(V+E)