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

위상정렬 알고리즘은 순서가 정해진 작업을 차례로 수행해야 할 때 사용한다.

 

순서의 일부만 나타낸 list를 가지고(graph의 edge와 같이) 전체 순서를 찾는 방식이다.

위상정렬 알고리즘의 가장 중요한점은

 

제일 처음에 있는 head는 자신을 가르키고 있는 노드가 없다는 점이다

 

이게 무슨 말이냐

 

다음과 같은 그래프가 있을 때 자신을 가르키는 노드(진입차수)가 없는 노드는 1번 뿐이다.

 

따라서 다음 그래프의 시작점은 1인 것이다.

 

따라서 각 노드의 진입차수를 표로 관리한다.

 

따라서 시작점은 1번인 것이다.

 

1번이 시작이면 이제 1번 노드를 삭제하고 진입차수를 다시 계산한다.

정확히 말하면 다시 계산이 아닌 1번 노드와 연결된 노드들을 1씩 빼는 것이다.

 

이 때 진입차수가 0인 노드가 다음 순서이다.

이런식으로 하면 BFS로 처리하면 된다. 

사실 DFS로 Stack으로 관리해도 되지만 일단은 BFS인 Queue로 구해 보겠다.

 

 

다음 노드인 2를 poll 한 뒤 진입차수가 0인 노드를 추가한다(4)

 

 

3번 노드를 제거한 뒤에도 진입 차수가 0인 노드가 없기 때문에 이번 단계에서는 추가되는 노드가 없다. 

 

 

 

따라서 Task 순서는 1 -> 2 -> 3 -> 4 -> 5 -> 6이다

 

 

출처: https://m.blog.naver.com/ndb796/221236874984