사이클이 없는 방향 그래프의 모든 노드를 순서대로 나열하는 것
ex) 대학교 선수과목 이수체계도
[위상정렬 알고리즘을 쓸 수 있는 조건]
1. 방향이 있는 그래프
2. 사이클이 없는 그래프
즉, 사이클이 없는 방향 그래프라 할 수 있는데 이를 DAG(Direct Acyclic Graph)라고도 한다.
DAG인 경우 위상정렬 알고리즘을 사용할 수 있다.
핵심은 각 노드의 진입차수(indegree)를 구하고 이를 통해 순서를 정하는 것이다.
진입차수란 화살표의 끝이 해당 노드에 들어오는 수다.
예를 들어 A -> B 그래프가 있다면 A의 진입차수는 0이고 B의 진입차수는 1이다.
그래서 맨처음 진입차수가 0인 노드가 루트노드이므로, 루트노드부터 화살표를 하나씩 지우는 작업을 통해 알고리즘이 구현된다.
A -> B -> C 그래프가 있을 때 루트노드 A를 결과 리스트에 넣고 연결된 화살표를 지우면 B의 진입차수가 1에서 0으로 줄어드므로 탐색 대상이 되는 것이다. 이를 큐에 넣어주는 작업을 그래프가 끝날 때까지 해주면 된다.
[요약]
1. 진입 차수가 0인 노드를 큐에 삽입한다.
2. 큐에서 원소를 꺼내 해당 원소에 연결된 화살표를 제거한다.
3. 화살표를 제거한 후 진입 차수가 0이 된 노드를 큐에 삽입한다.
4. 위 과정을 반복한다.
시간복잡도 : O(V+E)
아래와 같이 큐로 구현가능하고, DFS를 이용하면 스택으로도 구현할 수 있다.
큐에 한번에 2개 이상이 들어가는 경우 순서가 달라지므로 결과값이 여러개가 될 수 있다.
import sys
from collections import deque
input = sys.stdin.readline
V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]
indegree = [0] * (V+1)
for i in range(E):
a, b = map(int, input().split())
graph[a].append(b) # a -> b
indegree[b] += 1 # b의 진입차수 증가
def topology_sort():
result = []
queue = deque()
# 진입차수가 0인 노드 찾기(그래프의 맨처음 찾기)
for i in range(1, V+1):
if indegree[i] == 0:
queue.append(i)
while queue:
cur = queue.popleft()
result.append(cur)
# 해당 원소와 연결된 노드들의 진입차수에서 1빼기
for i in graph[cur]:
indegree[i] -= 1
if indegree[i] == 0:
queue.append(i)
for i in result:
print(i, end=' ')
topology_sort()
- 그래프에서 방문하지 않은 노드면 DFS를 수행
- DFS가 끝나면 해당 노드를 스택에 추가(정렬된 노드)
- 스택에서 하나씩 꺼내면 위상 정렬된 노드들을 얻을 수 있음
import sys
input = sys.stdin.readline
V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]
for i in range(E):
a, b = map(int, input().split())
graph[a].append(b) # a -> b
def topology_sort():
N = len(graph)
stack = []
visited = [0 for _ in range(N)]
for i in range(1, N):
if visited[i] == 0:
dfs(i, stack, visited)
result = []
while len(stack) != 0:
result.append(stack.pop())
for i in result:
print(i, end=' ')
def dfs(v, stack, visited):
visited[v] = 1
for i in graph[v]:
if visited[i] == 0:
dfs(i, stack, visited)
stack.append(v)
topology_sort()