위상 정렬 (Topological Sorting)

위상 정렬

정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘

사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'

 

진입차수와 진출차수

• 진입 차수 : 특정한 노드로 들어오는 간선의 개수
• 진출 차수 : 특정한 노드에서 나가는 간선의 개수

 

 

위상 정렬 알고리즘 동작 과정

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   ① 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   ② 새롭게 진입차수가 0이 된 노드를 큐에 삽입

 

 

위상 정렬의 특징

• 사이클이 없는 방향 그래프(DAG)에 대해서만 수행할 수 있다. 

※ DAG(Direct Acyclic Graph) : 순환하지 않는 방향 그래프

• 위상 정렬에는 여러가지 답이 존재할 수 있다. 
• 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단
  왜냐하면, 사이클에 포함된 원소는 큐에 들어가지 못하게 됨
• 보통 큐로 구현하지만, 스택을 이용한 DFS로도 구현 가능