위상 정렬

위상 정렬(Topology Sort)이란?

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

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

유의 사항

1. 위상 정렬은 항상 유일한 값으로 정렬되지 않는다.(정답이 여러개일 수 있다)
2. 사이클이 존재하면 노드간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

위상 정렬의 원리

진입 차수: 자기 자신을 가리키는 엣지의 개수

1. ArrayList로 사이클이 없는 그래프를 표현

진입 차수 배열 D를 아래 그림과 같이 업데이트한다.

*1에서 2, 3을 가리키고 있으므로 D[2], D[3]을 각각 1만큼 증가

2. 진입 차수가 초기화된 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 위상 정렬 배열에 저장, 그 후 ArrayList에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 감소

위의 그림에서 진입 차수가 0인 노드 1을 선택 후 2, 3의 진입 차수를 1씩 감소시켜 D[2], D[3]를 0으로 만들었다.
이 과정을 모든 노드가 정렬될 떄까지 반복한다.
만약 여기서 2, 3 중 3을 그 다음으로 선택했다면 3이 우선 위상 정렬 배열에 들어가게 된다.(늘 같은 정렬 결과를 보장하지 않는다.)

3. 최종 정렬 결과