위상 정렬(Topology Sort)

 

 

위상정렬이란?

 

방향 그래프에서 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 이다.

 

 

위상정렬의 특징

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

 

 

위상정렬의 흐름

 

 

1. 진입차수가 0인 정점을 선택

2. 선택된 정점과 연결된 간선들을 제거

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

 

 

 

위상정렬과 관련된 문제

 

백준

• 작업 : https://www.acmicpc.net/problem/2056
• 게임 개발 : https://www.acmicpc.net/problem/1516
• 줄 세우기 : https://www.acmicpc.net/problem/2252

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

도움을 준 사이트 : 

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

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html