[알고리즘] 위상정렬(topological sorting)

위상정렬

• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
• 선수 과목을 고려한 학습 순서 설정 등의 문제에서 사용
• 진입 차수 : 특정한 노드로 들어오는 간선의 개수
• 진출 차수 : 특정 노드에서 나가는 간선의 개수

구현방법

• DFS 또는 큐를 활용하여 구현
• 큐를 활용한 경우의 동작과정
  1. 진입 차수가 0인 모든 노드를 큐에 넣는다
  2. 큐가 빌 때까지 3-4번의 과정 반복
  3. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
  4. 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다
• 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같음
  

특징

• DAG(Direct Acyclic Graph) 순환하지 않는 방향 그래프를 만족해야 함
• 여러가지 답이 존재할 수 있음
  - 큐에 들어가는 원소가 2개이상인 경우
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단
• 사이클이 포함된 원수 중에서 어떠한 원소도 큐에 들어가지 못함
• 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수 있음

성능

• 위상 정렬을 위해 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거
• 한번 큐에 들어간 노드는 새로 큐에 들어가지 않음
• 시간 복잡도 - O(V+E)