Algorithm | Sort : 위상 정렬

위상 정렬(Topological Sort) ?

 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것이다. 위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조이다. 

 

 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프는 여러 위상 정렬이 가능하다. 

위상 정렬 구현(in JAVA)

import java.util.ArrayDeque;
import java.util.ArrayList;

public class TopologicalSort {
  private ArrayDeque<Integer> queue;
  private StringBuilder sb;

  public TopologicalSort() {
    queue = new ArrayDeque<>();
    sb = new StringBuilder();
  }

  // 진입 차수가 기록된 배열, 간선 정보가 저장된 배열을 매개변수로 받아 정렬 결과 출력하는 함수
  public void sort(int[] indegree, ArrayList<Integer>[] listArr) {
    for (int i = 0; i < indegree.length; i++) {
      if(indegree[i] == 0) {  // 선행 조건이 없는 노드를
        queue.add(i); // 추가한다
      }
    }
    while(!queue.isEmpty()) { // 큐가 빌 때 까지 반복
      int node = queue.peek();  // 노드를 하나 꺼낸다.
      sb.append(node + " ");  // 순서를 출력할 수 있도록 스트링 빌더에 저장
  
      for (int i = 0; i < listArr[node].size(); i++) {
        int linkedNode = listArr[node].get(i);  // 연결된 노드를 저장하는 변수
        indegree[linkedNode]--; // 진입 차수 감소
        if(indegree[linkedNode] == 0) queue.add(linkedNode);  // 진입차수가 0이라면 큐에 추가
      }
    }

    System.out.println(sb.toString());
  }
}

위상 정렬을 큐를 이용하여 구현해보았다. 진행 순서는 다음과 같다.

 

0. 제일 먼저 진입 차수가 0인 정점을 큐에 추가 (아무런 선행 조건이 없는 정점부터)

1. 큐에 저장된 정점를 하나 꺼낸다.

2. 꺼낸 정점과 연결된 정점을 찾아 선행되어야 할 정점을 처리했으므로 연결된 정점의 진입 차수를 하나 낮춘다.

3. 만약 진입 차수가 0이라면(선행 정점을 모두 처리한 경우) 큐 대기열에 추가

4. 큐가 빌 때 까지 1 ~ 3번 반복

---

Reference

 

· 위상 정렬이란? - https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

· 위키백과 위상정렬 - https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

· 위상 정렬 - https://m.blog.naver.com/ndb796/221236874984