알고리즘 - 위상 정렬

위상 정렬

---

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

시간 복잡도 - O(V + E) V: 노드 수, E: 에지 수

위상 정렬은 노드 간의 순서를 결정해준다.

※ 항상 유일한 값으로 정렬되지 않는다. 즉, 정답이 여러 개 일수도 있다.

위상 정렬의 핵심 이론

초기 세팅

1. 인접 리스트를 만들고 진입 차수를 초기화해준다.

진입 차수 연산

2. 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다.

3. 노드가 가리키는 노드들의 진입 차수를 1씩 빼준다.

※ 진입 차수(자기 자신을 가리키는 에지의 개수)