[Algorithm] 위상 정렬

위상 정렬

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

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

진입 차수 배열 D를 다음과 같이 업데이트 합니다.

• 진입 차수는 자기 자신을 가리키는 에지의 개수입니다.
• 1에서 2, 3을 가리키고 있으므로 $D[2], D[3]$을 각각 1씩 증가시킵니다.

진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 추가합니다. 그 후 해당 노드가 가르키는 노드 즉, 연결되어 있는 노드의 진입 차수를 1씩 감소시킵니다.

이후 모든 노드가 정렬될 때까지 위를 반복합니다.

• 만약 2가 아닌 3을 선택했다면 2보다 3이 우선적으로 정렬되는 결과가 나왔을 것 입니다.
• 위상 정렬은 늘 같은 정렬 결과를 보장하지 않습니다.