[알고리즘] 위상 정렬 (Topology Sort) 정리

0. 위상 정렬이란? 이번에 정리해 볼 알고리즘은 위상 정렬(topology sort)입니다. 위상 정렬은 선행 순서가 정해져있는 작업을 할 때, 이 순서를 위반하지 않고 작업을 처리하는 순서를 찾고 싶을 때 사용하는 알고리즘입니다. 위상 정렬은 DAG(Directed Acyclic Graph)에서만 적용할 수 있는데, 여기서 DAG란 사이클이 없는 방향이 있는 그래프를 의미합니다. 이는 그래프에서 사이클이 발생하는 경우 위상 정렬을 이용할 수 없기 때문입니다. 1. DAG(Directed Acyclic Graph) 예시들! 위와 같은 그래프를 DAG라고 할 수 있으며, 일반적으로 아래와 같은 실제 예시에 대입해서 해야 하는 일의 순서를 정하고 싶을 때 위상 정렬을 주로 사용합니다. 간단한 DAG 예시 2. 위상 정렬(Topology Sort)의 문제 해결 방식 진입 차수가 0인 정점을 큐(queue) 자료 구조에 삽입합니다. 순서는 상관없이 큐에 삽입한다. 큐에서 정점을 하나 가져...

원문링크 : [알고리즘] 위상 정렬 (Topology Sort) 정리