[알고리즘] 위상 정렬
2022. 10. 9. 18:03
1. 위상 정렬 (Topology Sort)
- 순서가 정해져 있는 작업을 차례로 수행해야 할 경우 그 순서를 결정해주기 위해 사용하는 알고리즘
- 사이클이 발생하지 않는 방향 그래프 DAG(Directed Acyclic Graph)에만 적용 가능
- 사이클 그래프에서는 시작점이 존재하지 않으므로 적용 불가능
- 현재 그래프가 위상 정렬이 가능한지 & 위상 정렬 결과는 무엇인지 알 수 있음
- 시간 복잡도 O(V + E)
2. 위상 정렬 알고리즘 순서
1) 집입차수가 0인 정점을 큐에 삽입
2) 큐에서 원소를 꺼내 연결된 모든 간선 제거
3) 간선 제거 이후 진입차수가 0인 정점 큐에 삽입
4) 큐가 빌 때까지 위 과정 반복. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과.
3. 예시 문제
2022.10.09 - [코딩테스트 (JS)/DFS | BFS] - [JS] Course Schedule
[JS] Course Schedule
🔒 문제 (LeetCode 207) There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] ind..
timemash.tistory.com
2022.10.09 - [코딩테스트 (JS)/DFS | BFS] - [JS] Course Schedule II
[JS] Course Schedule II
🔒 문제 (LeetCode 210) There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] ind..
timemash.tistory.com
'알고리즘' 카테고리의 다른 글
| 최대공약수(GCD), 최소공배수(LCM) 알고리즘 (0) | 2022.11.02 |
|---|---|
| [알고리즘] 순열과 조합 알고리즘 (0) | 2022.05.15 |
| [알고리즘] 이진트리의 순회 - 전위 순회, 중위 순회, 후위 순회, 레벨 순회 (0) | 2021.08.05 |
| [알고리즘] 이진 탐색 (Binary Search) (0) | 2021.07.03 |
| [알고리즘] 다익스트라 알고리즘 (0) | 2021.06.15 |