위상정렬_TopologicalSort

위상정렬(Topological Sorting)

• 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘.
• 사이클이 없는 방향, 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것.

진입차수와 진출차수

• 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수
• 동작과정
  • 큐를 이용해 구현한다.
  1. 진입차수가 0 인 노드를 큐에 넣는다.
  2. 큐가 빌 때까지 다음의 과정을 반복한다
     1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
     2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다.
  • 위상정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG)이여야 한다.

위상정렬의 특징

• 위상정렬은 사이클이 없는 방향그래프(DAG)에 대해서만 수행할 수 있다.
  • DAG(Direct Acyclic Graph) : 순환하지 않는(사이클이 없는) 방향 그래프
• 위상정렬에서는 여러가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답이 존재할 수 있다는 의미다.
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
• 보통 큐로 구현하나 스택을 이용한 DFS를 이용해 위상정렬을 구현할 수 있다.
• 시간복잡도 O(V+E)