위상 정렬 (Topology Sort)

위상 정렬(Topology Sort)이란?

어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘이다.

위상 정렬의 특징

• 하나의 방향 그래프에는 여러 위상 정렬이 가능하다.
• 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라 한다.
• 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다.
  
  

순서도

1. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택

   • 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다.
   • 초기에 간선의 수가 0인 모든 정점을 큐에 삽입
     
     

2. 선택된 정점과 여기에 부속된 모든 간선을 삭제

   • 선택된 정점을 큐에서 삭제
   • 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소
     
     

3. 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료
   
   

추천 문제

• 큐를 이용한 위상 정렬 : 줄 세우기 BOJ 2252
• 우선순위 큐를 이용한 위상 정렬 : 문제집 BOJ 1766
• 여러 위상 순서 중 가장 짧게 걸리는 위상 정렬 방법 구하기 : 작업 BOJ 2056, 게임개발 BOJ 1516