위상정렬

 

개념

---

위상정렬이란 directed graph에서 꼭짓점을 방향성을 거스르지 않도록 정렬하는 방법이다. 실생활에서 대표적인 예시가 바로 선수과목(prerequisite)이다.

 

알고리즘

---

구현하는 방법은 아래와 같다.

1. 연결성에 대한 정보를 가지고 인접리스트를 만든다.
2. 이를 기반으로 in-degree(해당 vertex로 들어오는 선의 갯수) 정보를 담은 배열을 만든다.
3. in-degree가 0인 vertex를 stack에 담는다.
4. stack에서 pop하고 해당 vertex와 연결된 점들의 in-degree를 -1 한다.
5. 3과 4를 반복하며 stack에서 pop 해줄 때마다 answer 리스트에 담으면 해당 결과가 위상정렬의 결과가 된다.

 

아래와 같은 그래프가 있다고 하면, in-degree(진입차수) 리스트는 아래와 같다. stack은 처음엔 비어있는 상태이다.

처음에 in-degree가 0인 0과 1이 stack에 push 된다.

stack에서 1을 pop하고 1과 연결된 3,4의 in-degree를 -1 해준다. 그럼 4의 in-degree가 0이 되므로 4를 stack에 push해준다.

다시 stack에서 4를 pop하고 4와 연결된 5의 in-degree를 -1 해준다.

stack에서 0을 pop하고 0과 연결된 2,3의 in-degree를 -1 해준다. 그럼 2의 in-degree가 0이 되므로 2를 stack에 push해준다.

stack에서 2를 pop하고 2와 연결된 3,5의 in-degree를 -1 해준다. 그럼 3의 in-degree가 0이 되므로 stack에 push 해준다.

stack에서 3을 pop하고 3과 연결된 5의 in-degree를 -1 해준다. 그럼 5의 in-degree가 0이 되어 stack에 push 해준다.

stack에서 5를 pop하고 더 이상 vertex가 남아 있지 않으니 종료한다. stack에서 pop할 때마다 answer 리스트에 담아주면 이 결과가 바로 위상정렬의 결과이다. (위상정렬의 결과는 답이 1가지가 아닐 수도 있다.)

 

왜 in-degree를 사용하면 위상 정렬이 될까? 이유는 간단하다. 조금 생각해보면, 위상 정렬이란 것이 결국 vertex간의 "위상" 즉, 우선 순위를 따져 정렬하는 것이기 때문이다. 처음에 in-degree가 0인 vertex를 찾는다는 것은 결국 그 vertex들 앞에 아무것도 오지 않아서 해당 vertex들이 맨 처음에 와야 한다는 뜻이다. 다음으로 stack에서 pop하고 해당 vertex와 연결된 vertex들의 in-degree를 -1해서 같은 과정을 반복하는 것도 같은 이치이다. 이를 반복하면 결국 위상정렬의 결과를 얻어낼 수 있는 것이다.

 

참고

---

https://sexy-developer.tistory.com/56