위상정렬 (Topology Sort)

정의

방향이 있는 그래프(DAG, Directed Acyclic Graph)에서 순서를 지켜 정렬하는 알고리즘

• cycle이 없는 경우에만 수행 가능
• 여러개의 정답이 가능

💡 의존 관계를 해결하며 올바른 순서를 찾는 문제에 적합!

구현

BFS(queue) 방식

1. 진입차수가 0인 노드(초기노드)를 큐에 삽입
2. 큐가 빌 때까지 아래를 반복
   1) 큐에서 pop한 노드에서 나가는 간선 제거 ➡️ 연결노드의 진입차수 감소
   2) 진입차수가 0인 노드를 큐에 삽입

만약 모든 노드를 방문하기 전에 반복이 종료된다면(큐가 빈다면) cycle이 있는 것
➡️ 위상정렬 불가능

시간복잡도 O(N+M)

DFS(stack) 방식

1. 모든 노드를 탐색하여 방문하지 않은 노드에서 DFS 수행
2. DFS를 수행하면서 재귀 종료시점에 스택에 노드 삽입
3. 모든 노드 방문 후, 스택에 저장된 순서대로 출력 (반대 순서가 정답이 됨)

시간복잡도 O(N+M)