위상 정렬이란?

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다.

= 순서가 정해진 노드들을 정렬하는 문제

시간 복잡도 : O(V+E)

위상 정렬에서는 항상 유일한 값으로 결정되지 않는다.

또한 사이클이 있으면, 노드 간의 순서를 정할 수 없으므로 사이클이 있을 땐 위상정렬을 적용할 수 없다.

위상 정렬의 핵심 이론

✅위상 정렬의 원리 이해하기

용어

진입 차수 : 자기 자신을 가리키는 에지의 개수