위상정렬(Topological Sort)

위상정렬의 개념

 

위상정렬이란 순서가 있는(즉, 방향이 있는) 작업을 차례로 진행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프(Directed Acyclic Graph)의 모든 노드를 주어진 "선행순서를 위반하지 않으면서" 나열하는 것이다.
예시: 대학교 선수과목, 공장의 작업 순서, 요리 순서...

DAG(사이클 없는 방향 그래프)

특정 정점을 진행하기 위해 거쳐야 하는 정점의 수(간선으로 연결된)를 진입차수라 하고
특정 정점에서 넘어가야 할 다음 정점의 수를 진출차수라고 한다.
그 중 선행 조건이 되는 진입차수가 중요하다.

 

 

위상정렬의 특징

 

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

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

3) 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입차수가 0인 정점이 없다면 => 싸이클 있는 그래프로 실행 불가

 

 

위상정렬의 구현과 동작

 

1) Queue를 이용하여 구현하며 Queue에서 꺼내지는 순서(=Queue에 들어온 순서)가 위상 정렬을 수행한 결과이다.

* 모든 정점을 방문하기 전 queue가 공백 상태라면 사이클이 존재하는 그래프라는 의미임

 

(1) 진입차수가 0인 모든 노드를 queue에 삽입

(2) queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 확인하고
      이에 연결된 노드를 정점에서 제거(연결된 노드의 진입 차수를 감소시킴) => 진입차수 0이 되는 경우 발생

(3) 새롭게 진입 차수가 0이 된 노드를 queue에 삽입

(4) queue가 공백이 될 때까지 2) ~ 3) 반복 수행

 

2) Stack을 이용하여 구현 (잘 사용하지 않음)

* 시스템 스택(재귀함수 위함), 위상 정렬 스택 필요

 

(1) 진입차수가 0인 모든 노드에서 DFS 수행

(2) DFS 수행

  - 해당 노드 방문 표시

  - 인접하고 아직 방문 전인 노드 DFS 호출

  - 함수 return 전 stack에 현재 노드 저장

(3) Stack이 공백이 될 때까지 pop => 꺼낸 순서 역순의 경우 위상 정렬을 수행한 결과임

 

 

위상정렬의 시간복잡도: O(N+E)