위상 정렬

  • 유향 그래프의 정점들의 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
  • 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘이다.
  • 위상 정렬을 가장 잘 설명해 줄 수 있는 예로 교육과정의 선수과목(prerequisite) 구조를 예로 들 수 있다.
  • 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다.


  • 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다.
  • 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다.
  • 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다.
  • 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다.

위상 정렬 - 결과

  • 위상 정렬이 가능한지 여부
    • 사이클 발생 여부 확인 가능
  • 가능하다면 정렬된 결과

위상 정렬 - 구현방식

  • BFS를 이용한 구현
  • DFS를 이용한 구현

위상 정렬 구현

BFS 사용

TopologySortTest.java

1. 진입 차수가 0인 노드(시작점, 선행 작업이 없음)를 큐에 모두 넣는다.
  진입차수 : 다른 정점에서 나로 들어오는 간선 수
2. 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 인접한 노드의 간선을 제거한다.
  -> 인접한 노드의 진입 차수를 1 감소시킨다.
3. 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.
  • 큐가 공백 큐 상태가 될 때까지 2-3 작업을 반복한다.
    • 모든 노드가 다 처리되었다면 위상 정렬 완성
    • 모든 노드가 처리되지 않았다면 사이클링이 발생했다는 의미