[알고리즘] 그림으로 알아보는 위상 정렬(Topology sort)

위상정렬(Topology sort)?

순서가 정해져 있는 노드들을 정렬하는 알고리즘입니다. 그래프에서 순서는 방향성으로 나타내며, 정해진 순서를 지키면서 모든 정점을 정렬하는 것이 목표입니다.

위상정렬 시 주의해야할 점이 있습니다.

1. 하나의 그래프에서 위상정렬 시 여러가지 경우의 수가 나올 수 있습니다.
2. 그래프에 순환하는 노드들이 존재할 시 위상정렬을 실시할 수 없습니다.

위상정렬 구동원리

위상정렬을 수행하는 방법은 2가지가 있습니다.

1. 각 노드들의 진입차수를 활용하는 Queue 방법
2. DFS를 활용하는 Stack 방법

Queue방법 구현과정

Queue를 이용한 위상정렬을 위해 필요한 정보는 각 노드들의 진입차수입니다. 진입차수는 해당 노드를 가르키고 있는 노드의 수를 뜻합니다. 아래 그림에서 3번노드의 진입차수는 3, 6번 노드의 진입차수는 2, 1번노드의 진입차수는 0입니다.

Queue 방법은 진입차수가 없는 노드는 현재 과정에서 실행되도 순서에 문제가 없다는 점을 이용합니다. 개괄적인 순서는 다음과 같습니다.

1. 1번 노드부터 순회하면서 진입차수가 0인 노드를 찾습니다.
2. 진입차수가 0인 노드는 Queue에 삽입하고, 해당 노드의 간선들을 모두 제거합니다.(가리키고 있는 노드들의 진입차수를 하나씩 줄입니다.)
3. 위 과정을 반복합니다.

Stack방법 구현과정

Stack을 이용한 위상정렬을 위해 필요한 정보는 각 노드들의 방문여부입니다. 일반적인 DFS에서 사용하는 방문여부 배열과 동일합니다.

Stack 방법은 DFS 과정에서 막다른 노드에 다다르면 뒤로 돌아가면서 스택에 저장합니다. 뒤로 돌아가면서 Stack에 넣기 때문에 순서가 느린 노드부터 Stack에 들어가 모든 Stack이 채워지면 Stack을 뒤집어줘야 합니다. 개괄적인 순서는 다음과 같습니다.

1. 1번 노드부터 순회하면서 DFS를 실행하며 방문여부 저장합니다.
2. DFS 진행 중 막다른 노드(다른 노드를 가리키고 있지 않은 노드)에 다다르면 Stack에 삽입합니다.
3. DFS 탐색이 끝나면 다음 노드를 DFS 탐색하며 위 과정을 반복합니다.

마무리

Queue 방식과 Stack 방식을 위상정렬 값을 보면 서로 다른 것을 알 수 있습니다. 위에서 언급했던 바와 같이 하나의 그래프에서 위상정렬 시 여러가지 경우의 수가 나올 수 있음을 확인하였습니다. 문제의 특성에 따라 Stack 방법과 Queue 방법을 적절히 활용하는것이 좋습니다.