위상 정렬(Topology Sort) 알고리즘

위상 정렬(Topology Sort) 알고리즘

사이클이 없는 방향 그래프에서 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 알고리즘

 

• 특징

- 항상 유일한 값으로 정렬되지 않는다.

- 사이클이 없어야 한다.

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

 

 

위상 정렬 수행 과정

1. 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트한다.

 

* 진입 차수(In-Degree) : 자기 자신으로 들어오는 에지의 개수 

[ 예시 ]

 

 

2. 진입 차수가 0인 노드를 큐에 저장한다.

[ 예시 ]

진입 차수가 0인 노드 1을 선택하여 위상 정렬 배열에 저장

 

3. 큐에서 데이터를 꺼내 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.

[ 예시 ]

[ 예시 ]

인접 리스트 [1]의 연결값 2, 3의 진입 차수를 1씩 빼기

 

4. 새롭게 진입 차수가 0이 되는 노드를 큐에 삽입한다.

 

5. 큐가 빌 때까지 2 ~ 4번의 과정을 반복한다. 

[ 예시 ]

 

 

• 모든 원소를 방문하기 전에 큐가 빈다. = 사이클이 존재한다.
• 위상 정렬을 수행한 결과 ⇒ 1 ~ 5번의 과정을 수행하는 동안 큐에서 빠져나간 노드를 순서대로 출력
• 위상 정렬의 여러 가지 답안이 존재하는 경우 ⇒ 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.