알고리즘
위상 정렬 (Topological Sorting)
문군_
2025. 2. 1. 14:33
- 정렬 알고리즘의 일종
- 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용
- 사이클이 없는 방향 그래프의 모든 노드를
방향성에 거스르지 않도록 순서대로 나열하는 것
진입차수와 진출차수
- 진입차수 (Indegree): 특정한 노드로 들어오는 간선의 개수
- 진출차수 (Outdegree): 특정한 노드에서 나가는 간선의 개수
위상 정렬 알고리즘 동작 과정
1. 진입 차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
a. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
b. 새롭게 진입차수가 0이 된 노드를 큐에 삽입
⇒ 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과
위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG) 여야만 한다.
위상 정렬의 특징
- 위상 정렬은 사이클이 없는 방향 그래프(DAG) 에 대해서만 수행할 수 있다.
- 위상 정렬에는 여러 가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재할 수 있다는 의미이다.
- 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다.
- 보통 큐를 사용하나 스택을 이용한 DFS로도 구현이 가능하다.
- 시간 복잡도는 O(V + E)
- 차례대로 모든 노드(V)에 대해, 해당 노드에서 출발하는 간선(E)을 차례대로 제거해야 하기 때문이다.