[Algorithm] 36강 : 위상정렬 알고리즘의 정의와 구현

위상정렬 1.1 위상정렬 이란? 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미 1.2 진입 차수 / 진출 차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 1.3 위상 정렬 알고리즘 동작과정 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다 큐에서 원소를 꺼내 해당노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. 이 과정을 계속해서 반복한다. 또한, 같이 0 이되..