위상정렬

위상정렬 topology sort

 

사이클이 없는 방향 그래프에서 노드 순서가 찾는 알고리즘

 

항상 유일한 값으로 정렬되지 않음

사이클이 있으면 명확한 순서 정의 불가

 

아래의 과정을 반복하여 값을 구한다.

진입차수가 0인 노드를 선택하고 저장함

인접 리스트에서 선택된 노드가 가리키는 진입차수 -= 1