오늘은 위상 정렬의 개념에 대해 공부해보았습니다.
📡위상정렬?
위상 정렬(Topology Sort)이란 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미합니다.
특정한 노드로 들어오는 간선의 개수를 진입차수라 합니다.
✔️ 1. 진입차수가 0인 노드를 큐에 담습니다.
✔️ 2. 큐가 비어있을 때까지 다음의 과정을 반복합니다.
- 2-1 ) 큐에 담긴 노드를 꺼내어 해당 노드에서 출발하는 모든 간선을 그래프에서 제거합니다.
- 2-2 ) 진입차수가 0인 노드를 큐에 담습니다.
1. 진입차수가 0인 노드 1을 큐에 담습니다.
2. 큐에 담긴 노드 1을 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.
3. 큐에 담긴 노드 2를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.
4. 큐에 담긴 노드 5를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.
5. 큐에 담긴 노드 3를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드가 존재하지 않으므로 넘어갑니다.
6. 큐에 담긴 노드 6를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.
7. 큐에 담긴 노드 4를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.
8. 큐에 담긴 노드 7을 꺼내고 출발하는 간선과 전입차수가 0인 노드가 존재하지 않습니다. 이렇게 큐에서 꺼내어진 노드 순서대로 출력하여 위상 정렬을 마칩니다.
📡특징!
-
모든 원소를 방문하지 않았는데 큐가 비었다는 것은 사이클이 발생했다는 것을 의미합니다.
-
큐에 담기는 노드가 2개 이상인 경우, 위상 정렬된 후의 결과가 여러 개일 수 있습니다.
📡시간복잡도
위상 정렬을 위해 차례대로 모든 노드를 확인하면서,
각 노드에서 나가는 간선들을 하나씩 제거하는 과정을 거친다.
따라서, 위상 정렬의 사간복잡도는 O(V + E) 입니다.
