위상정렬 (Topological Sorting) 이란?
순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘.
ex) 선수과목을 고려한 학습 순서
조금 더 이론적인 설명은
`사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 을 의미한다.
다음 예시를 보자.
그림과 같이 3개의 과목이 있다고 가정하면,
세 과목을 모두 듣기 위해서 자료구조 → 알고리즘 → 고급 알고리즘 순서로 과목을 들어야 한다.
만약 자료구조 → 고급 알고리즘 → 알고리즘 (X) 순서로 과목을 듣는다고 하면, 해당 순서는 올바른 순서가 아니다.
🔎 진입차수와 진출차수
위상 정렬 알고리즘을 이해하기 위해서는 먼저 진입차수와 진출차수에 대해 알아야한다.
- 진입차수 (Indegree) : 특정한 노드로 들어오는 간선의 개수
- 진출차수 (Outdegree) : 특정한 노드에서 나가는 간선의 개수
🚗 위상정렬의 동작 과정
큐를 이용하는 위상 정렬 알고리즘의 동작 과정 은 다음과 같다.
- 진입차수가 0인 모든 노드를 큐에 넣는다.
- 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
즉, 각 노드가 큐에 들어온 순서가 위상정렬을 수행한 결과 이다!
그림과 함께 다시 보자. (그림 출처 : 이코테)
위 그림은 위상 정렬을 수행할 그래프이다. 이때 위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프 (DAG) 이여야 한다!
[step 0] 진입차수가 0인 모든 노드를 큐에 삽입. 현재 1번 노드의 진입차수만 0이므로 큐에 1번 노드만 삽입하게 된다.
[step 1] 큐에 있는 1번 노드를 꺼낸다. 이후 1번 노드와 연결되어 있는 간선들을 제거한다. 그러면 2번 노드와 5번 노드의 진입차수가 0이 되고, 2번 노드와 5번 노드의 진입차수가 0이므로 큐에 삽입한다.
[step 2] 큐에 있는 2번 노드를 꺼낸다. 2번 노드와 연결되어 있는 간선들을 제거한다. 그러면 3번 노드의 진입차수가 0이 되므로 3번 노드를 큐에 삽입한다.
[step 3] 큐에 있는 5번 노드를 꺼낸다. 5번 노드와 연결되어 있는 간선들을 제거한다. 그러면 6번 노드의 진입차수가 0이 되므로 6번 노드를 큐에 삽입한다.
[step 4] 큐에 있는 3번 노드를 꺼낸다. 3번 노드와 연결되어 있는 간선들을 제거한다. 이번 단계에서는 새롭게 진입차수가 0이 되는 노드가 없으므로 넘어간다.
[step 5] 큐에 있는 6번 노드를 꺼낸다. 6번 노드와 연결되어 있는 간선들을 제거한다. 그러면 4번 노드의 진입차수가 0이 되므로 4번 노드를 큐에 삽입한다.
[step ~ ] 위와 동일한 로직으로 큐에 있는 노드를 꺼내고, 꺼낸 노드와 연결되어 있는 간선들을 제거한다. 새롭게 진입차수가 0이 되는 노드를 큐에 삽입한다.
[결과] 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7
※ 위상 정렬의 답안은 여러 가지가 될 수 있다는 점이 특징이다.
따라서 1 -> 5 -> 2 -> 3 -> 6 -> 4 -> 7 도 하나의 답이 될 수 있다.
🔧 위상 정렬의 특징
- 위상 정렬은 순환하지 않는 방향 그래프 (DAG) 에 대해서만 수행할 수 있다.
※ DAG (Direct Acyclic Graph) : 순환 하지 않는 (= 사이클이 없는) 방향 그래프
- 위상 정렬에서는 여러가지 답이 존재할 수 있다. (한 단계에서 큐에 원소가 2개 이상 들어가는 경우)
- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
왜냐하면, 사이클에 포함된 원소 중에서 해당되는 어떤 원소도 큐에 들어가지 못하게 되기 때문이다.
- 보통 큐로 구현하나, 스택을 이용한 DFS를 통해 위상정렬을 구현할 수도 있다.
🖥️ Python Code
def topology_sort():
queue = deque()
# 진입차수가 0인 모든 노드를 큐에 넣음
for i in range(1,N+1):
if indegree[i] == 0:
queue.append(i)
while queue:
current = queue.popleft()
# 현재 노드와 연결된 모든 노드의 진입차수 감소
for next in graph[current]:
indegree[next] -= 1
if indegree[next] == 0:
queue.append(next)
달려