위상정렬

 

 

Topological Sort

 

 

 

그래프 자료구조에 대해 정렬을 수행할 때 위상정렬을 사용한다.

위상정렬은 DAG 그래프에 대해서만 수행 할 수 있다. (사이클이 없고 방향성이 있는 그래프)

 

위상정렬을 통해 DAG에서 간선의 방향성에 따라 정점을 위상에 맞춰 정렬해보자.

 

 

 

 

 

N에서 K로 가는 간선이 있다면 N은 K보다 먼저 나타나야 한다.

위의 조건을 충족하면서 정점들을 나열하는 것을 위상정렬이라고 한다.

 

위의 조건 때문에, 사이클이 있는 그래프에 대해서는 위상정렬을 수행할 수 없다.

 

 

 

이제 위상정렬의 과정에 대해 알아보자.

 

 

 

 

제일 먼저 올 수 있는 정점은 들어오는 간선이 없는 정점이다.

 

 

 

 

 

위의 그래프에서 정점 1 9 7은 들어오는 간선이 없기 때문에 정렬을 수행한 결과 중 앞에 위치한다. (1 9 7 간의 순서는 상관없음)

 

그러니 큐를 선언하고 큐에 1 9 7 을 담아준다. (들어온 순서대로 작업을 수행해야 되기 때문)

 

그 후 그래프에서 1 9 7을 하나씩 제거해 보며 들어오는 간선이 없는 정점이 다시 생기는지 확인하고, 해당하는 정점이 생기면 자료구조에 그 정점을 넣어준다.

 

이 때 큐에서 제거되는 요소들은 배열이나 리스트에 넣어준다. (정렬이 완료된 요소들이다.)

 

 

https://13months.tistory.com/334

[백준] 2252 줄 세우기 - Java

 

 

 

관련 문제를 많이 풀어서 익숙해지자.