위상 정렬에 대해 설명하세요
Keyword
방향성, 비순환, 선후관계, InDegree
Script
위상정렬은 방향성 비순환 그래프에서 선후관계를 고려한 정렬 알고리즘입니다. 예를 들어 A 정점에서 B 정점으로 향하는 간선이 존재할 때, A가 B보다 앞쪽에 위치하도록 정렬하도록 설계된 알고리즘입니다.
위상정렬의 핵심은 특정 정점으로 향하는 간선의 개수인 InDegree를 활용하여 현재 0의 InDegree를 가지는 정점을 우선적으로 탐색하는 것입니다. 특정 정점이 탐색되면, 해당 정점이 가르키는 정점들의 InDegree를 감소시키고 앞선 과정을 반복합니다.
위상정렬의 시간복잡도는 모든 노드를 순회하면서 각 노드에서 출발하는 간선을 순차적으로 제거하기 때문에, 모든 노드와 간선을 확인하는 과정을 거쳐 O(V + E)의 시간복잡도를 가집니다.
Additional
0인 InDegree 탐지시 시간복잡도
매번 모든 과정에 있어서 0인 InDegree를 탐지하기 위해서는 InDegree를 줄이면서 동시에 InDegree가 0이 된다면, 다음 탐색할 정점을 나타내는 queue에 삽입하면 상수 시간복잡도로 0인 InDegree를 가지는 정점을 찾아낼 수 있다.
with programming