크래프톤 정글 주제별 탐구 -위상정렬-

정의

위상 정렬이란, 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것.

특징

먼저, 진입차수와 진출차수에 대해 알아야 한다.

• 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수

구현 방식

위상정렬은 DFS나 Queue를 이용해서 구할 수 있다.

Queue 방식

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

이를 통해 결과적으로 각 노드가 큐에 들어온 순서 가 위상정렬을 수행한 결과와 같다.