방향 그래프 (Directed Graphs) 깊이 탐험하기
지난 포스팅에서는 그래프 탐험 알고리즘인 DFS와 BFS에 대해 알아보았다. 이번에는 방향성을 가진 edge로 구성된 방향 그래프(Directed Graph, Digraph)에 대해 좀 더 깊이 파고들어 보고자 한다. 방향 그래프는 일방 통행 도로, 항공편, 작업 스케줄링 등 실생활의 다양한 상황을 모델링하는 데 유용하게 활용될 수 있다.
1. Reachability (도달 가능성)와 Connectivity (연결성)
방향 그래프에서 Reachability(도달 가능성)는 특정 정점에서 다른 정점으로 가는 경로가 존재하는지 여부를 의미한다. 예를 들어, 도시 A에서 도시 B로 가는 항공편이 있다면, 도시 A에서 도시 B로 도달 가능하다고 말할 수 있다.
Connectivity(연결성)는 그래프의 모든 vertex 쌍 간에 경로가 존재하는지 여부를 나타낸다. 방향 그래프에서는 강한 연결성(Strongly Connected)과 약한 연결성(Weakly Connected) 두 가지 개념이 존재한다.
- 강한 연결성(Strongly Connected): 모든 정점 쌍 간에 서로 도달 가능한 경로가 존재하는 경우. 즉, 어떤 정점에서 시작하더라도 다른 모든 정점으로 이동할 수 있다.
- 약한 연결성(Weakly Connected): 방향 그래프의 모든 간선을 무방향 간선으로 간주했을 때, 모든 정점 쌍 간에 경로가 존재하는 경우. 즉, edge의 방향을 무시하면 모든 정점이 연결되어 있다.
 |
| Reachability & Connectivity |
2. Transitive Closure
Transitive Closure는 방향 그래프에서 도달 가능성 정보를 제공하는 중요한 개념이다. 그래프 G의 transitive closure G*는 G와 동일한 vertex 집합을 가지며, G에서 u에서 v로 가는 경로가 존재하면 (u ≠ v), G*에는 u에서 v로 향하는 간선이 존재한다. 쉽게 말해, G*는 G의 모든 가능한 경로 정보를 담고 있는 그래프다.
 |
| transitive closure |
Floyd-Warshall Algorithm (플로이드-워셜 알고리즘)
Floyd-Warshall 알고리즘은 방향 그래프의 transitive closure를 계산하는 효율적인 알고리즘이다. 이 알고리즘은 동적 프로그래밍(Dynamic Programming) 기법을 사용하여 모든 정점 쌍 간의 최단 경로를 계산하는 과정에서 G*를 구한다. 시간 복잡도는 O(n^3)다. (n은 정점의 수)
Floyd-Warshall 알고리즘의 핵심 아이디어
- 정점에 1부터 n까지 번호를 부여한다.
- 1부터 n까지의 정점을 중간 정점(intermediate vertices)으로 사용하여 경로를 고려한다.
- 각 단계 k에서, 정점 1부터 k까지를 중간 정점으로 사용하여 i에서 j로 가는 경로가 존재하는지 확인하고, 존재한다면 Gk에 간선 (vi, vj)를 추가한다.
 |
| Floyd-Warshall algorithm example |
3. Topological Sorting (위상 정렬)
Topological Sorting(위상 정렬)은 방향 그래프의 정점들을 순서대로 나열하는 방법으로, 모든 edge (u, v)에 대해 u가 v보다 앞에 위치하도록 한다. 즉, 방향 그래프에서 선행 관계를 고려하여 정점을 정렬하는 것이다.
DAG (Directed Acyclic Graph, 방향성 비순환 그래프)
Topological Sorting은 DAG(Directed Acyclic Graph, 방향성 비순환 그래프)에서만 가능하다. DAG는 사이클이 없는 방향 그래프를 의미한다. 예를 들어, 선수 과목 관계를 나타내는 그래프는 DAG다.
 |
| DAG example |
Topological Sorting 알고리즘
Topological Sorting을 수행하는 알고리즘은 여러 가지가 있지만, DFS를 활용하는 방법이 대표적이다.
- DFS를 수행하며 각 정점의 방문이 끝나는 순서를 기록한다.
- 기록된 순서를 역순으로 뒤집으면 Topological Sorting 결과가 된다.
시간 복잡도: DFS를 사용하는 Topological Sorting의 시간 복잡도는 O(V + E)입니다. (V는 정점의 수, E는 간선의 수)
* outgoing edge가 없는 node(가장 마지막)부터 역순으로 incoming를 지워가며 topological sorting을 수행하는 알고리즘도 있다.
 |
| Topological ordering |
마무리하며
이번 포스팅에서는 방향 그래프의 Reachability, Connectivity, Transitive Closure, Floyd-Warshall 알고리즘, 그리고 Topological Sorting에 대해 알아보았다. 특히, transitive closure와 topological sorting은 방향 그래프를 분석하고 활용하는 데 중요한 개념이므로 꼭 기억해 두길 바란다. 다음 포스팅에서는 가중치 그래프(Weighted Graph)와 최단 경로 알고리즘(Shortest Path Algorithm)에 대해 알아보겠다.
추천글:
(https://hyeonb.blogspot.com/2024/06/dfs-bfs.html)
(https://hyeonb.blogspot.com/2024/06/graph.html)
