위상 정렬

[DockerIsFish]

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

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