[정렬] 위상 정렬

위상 정렬이란?

어떤 일을 하는 순서를 찾는 알고리즘이다.

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

위상 정렬의 특징

• 하나의 방향 그래프에는 여러 위상 정렬이 가능하다.

• 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라고 한다.

• 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면,

  위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다.

위상 정렬 이용하는 방법

• 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택을 하고 Queue에 모두 넣는다.

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

  • 선택되어진 정점을 Queue에서 제거
  • 선택된 정점에 속해있는 간선에 대해 간선의 수 감소

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

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