위키피디아에서 위상정렬의 개념을 찾아보면
위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
라고 나온다.
즉 방향그래프 내에서 선행 순서를 거스르지 않으면서 정점들을 배치하는 것이다.
위상정렬의 특징
- 위상정렬은 그래프의 순환이 일어나지 않을 때에만 가능하다.
따라서 위상정렬은 시작점이 존재하는 방향그래프(=비순환 유향그래프)에서만 가능하다. - 한 그래프 내에서 한 개 이상의 위상정렬이 가능하다.
위상정렬하는 방법
위상정렬을 하는 방법은 간단하다.
1. 진입차수가 0인 정점들을 먼저 배치하고 2. 배치하면서 그 정점에서 나오는 간선들을 제거한다. 3. 다음 진입차수가 0인 점을 찾아 반복한다.
쉽게 말하자면 자기 자신을 가리키는 화살표가 없을 때(모든 선행 순서가 완료되었을 때) 배치하면 된다는 것이다.
위상정렬은 큐를 이용한 방식과 스택을 이용한 방식이 있다.
내가 이해하기로는 BFS방식과 DFS방식 두 가지 인 것 같은데 스택을 이용한 DFS방식을 이용해보겠다.
우선 진입차수(자신을 가리키는 화살표의 개수)가 0인 정점을 스택에 넣어준다.
stack = [1, 4, 6]
그리고 stack의 가장 마지막 원소인 정점 6을 빼주면서 정점 6과 여기에서 나오는 간선(화살표)을 제거해준다.
stack = [1, 4]
answer = [6]
그럼 위 그림과 같이 정점 5의 진입차수가 0이 되므로 stack에 넣어준다.
stack = [1, 4, 5]
그리고 다시 스택의 마지막 원소인 정점 5를 스택에서 빼주며 위 과정을 반복한다.
stack = [1, 4]
answer = [6, 5]
이때는 진입차수가 0이 되는 새로운 점이 없으므로 stack[-1]인 4에 대해서 위 과정을 진행한다.
stack = [1]
answer = [6, 5, 4]
이때도 마찬가지로 진입차수가 0이 되는 새로운 점이 없으므로 stack에서 1을 빼준다.
stack = []
answer = [6, 5, 4, 1]
이때 정점 2의 진입차수가 0이 되므로 stack에 2를 넣어준다.
stack = [2]
그리고 다시 stack[-1]인 2를 빼준다.
stack = []
answer = [6, 5, 4, 1, 2]
마지막으로 정점 3의 진입차수가 0이 되므로 stack에 넣어주고
stack = [3]
위 과정을 진행하면
stack = []
answer = [6, 5, 4, 1, 2, 3]
6, 5, 4, 1, 2, 3 순으로 위상정렬이 완료된다.
*큐를 이용해 위상정렬을 하면 1, 4, 6, 2, 5, 3순으로 정렬이 되고 스택을 이용한 방식과 마찬가지로 맞는 정렬이다.
코드
위에서 설명한 내용을 코드로 작성하면 아래와 같다. (파이썬)
from collections import deque
N = 6 #점의 개수
routes = [[1, 2], [2, 3], [4, 3], [5, 3], [6, 5]] # 앞 원소에서 뒷 원소를 향하는 간선들
dots = [[] for _ in range(N + 1)] #각 점들이 가리키고 있는 점들(후순위에 있는 점들)
cnt = [0] * (N + 1) #점들의 진입차수
for route in routes:
a, b = route
dots[a].append(b)
cnt[b] += 1
#스택 이용
stack = [1, 4, 6]
answer = []
while stack:
target = stack.pop()
answer.append(target)
for dot in dots[target]:
cnt[dot] -= 1
if cnt[dot] == 0:
stack.append(dot)
print(answer)
#answer = [6, 5, 4, 1, 2, 3]
for route in routes:
a, b = route
cnt[b] += 1
#큐 이용
queue = deque([1, 4, 6])
answer = []
while queue:
target = queue.popleft()
answer.append(target)
for dot in dots[target]:
cnt[dot] -= 1
if cnt[dot] == 0:
queue.append(dot)
print(answer)
#answer = [1, 4, 6, 2, 5, 3]