위상 정렬

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

• 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다.
• 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

위상 정렬의 핵심 이론

위상 정렬의 원리 이해하기

1. 진입 차수를 이해해 보자. 진입 차수는 자기 자신을 가리키는 엣지의 갯수이다. 다음을 보면 ArrayList로 그래프를 표현하였다. 그래프는 사이클이 없는 상태이다.

1. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.

위상 정렬 배열 결과는 아래와 같다.

위상 정렬은 진입 차수 배열이 중요하다!

출처 - 하루코딩