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

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

핵심 이론

위상 정렬의 원리 이해하기

1. 진입 차수(in-dgree): 자기 자신을 가리키는 에지의 개수

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

• 위 과정을 모든 노드가 정렬될 때까지 반복
• 3을 먼저 선택하면 3이 우선 위상 정렬 배열에 들어감 → 늘 같은 정렬 결과를 보장하지 않음

• 위상 정렬 배열 결과

위상 정렬 = 진입차수 배열을 이용한 정렬