그래프 - 위상 정렬

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

기능	특징	시간 복잡도(노드 수: V, 엣지 수: E)
노드 간의 순서를 결정	사이클이 없어야 함	O(V + E)

 

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

또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없습니다.

 

위상 정렬의 핵심 이론

위상 정렬의 원리 이해하기

1. 진입 차수는 자기 자신을 가리키는 엣지의 개수입니다.