[Java] 위상 정렬(Topological Sort) 개념과 구현

---

위상 정렬이란

그래프 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘입니다.

 

위상 정렬이 가능하려면 DAG(Directed Acyclic Graph)이어야 합니다.

1. 방향성 O: Node A → Node B와 같이 두 노드 사이 방향이 있어야 합니다.
2. 사이클 X: A → B, B → A아 같은 사이클이 없어야 합니다.

 

예를 들어, 총 3개의 과목이 있고, 한 과목을 듣기 위한 선이수과목 관계가 표시되어 있습니다.

세 과목을 모두 듣는 코스는 `프로그래밍 기초  → C 프로그래밍  → 고급 C 프로그래밍`의 순서가 되어야 합니다.

`고급 C 프로그래밍  → C 프로그래밍  → 프로그래밍 기초` 순서는 안 되는 겁니다.

이처럼 그래프에서 방향성을 통해 적절한 순서를 찾는 것이 위상 정렬입니다.

---

알고리즘 구현

구현 전 알아야하는 용어가 있습니다.

• 진입 차수(Indegree)
  • 특정한 노드로 들어오는 간선의 개수
  • 아래 그래프에서 6의 진입 차수는 2
• 진출 차수(Outdegree)
  • 특정한 노드에서 나가는 간선의 개수
  • 아래 그래프에서 5의 진출 차수는 1

 

위상 정렬은 큐를 이용하여 다음과 같은 단계로 구현할 수 있습니다.

큐에서 꺼내지는 순서가 위상 정렬 결과입니다.

 

💯 위상 정렬 구현 공식

1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정을 반복한다.     1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.     2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다.

 

1단계에 따라,

진입차수가 0인 노드를 큐에 넣으면 노드 1이 처음으로 들어갑니다.

2-1단계에 따라 큐에 있는 노드 1을 꺼내고(=1이 출력됩니다) 노드 1을 삭제합니다.

이로써 새롭게 진입 차수가 0이 된 노드 2와 노드 5가 큐에 들어갑니다.

 

노드 2와 노드 5가 큐에 들어가는 순서는 요구사항에 따라 달리질 수 있습니다. 그냥 오름차순으로 넣었습니다.

 

노드 2와 노드 5까 큐에서 꺼내지고 그래프에서 삭제되면서

노드 3과 노드 6의 진입 차수가 0이 됩니다.

 

이어지는 과정은 그림으로 살펴보겠습니다.

 

 

 

큐가 비고, 모든 노드가 삭제되면서 정렬이 끝났습니다.

정렬 결과는 `1→2 →5 →3 →6 →4 →7`입니다.

 

---

Java로 구현

import java.util.*;

public class TopologicalSort {

  public static void main(String[] args) {
    int n = 7;  // 노드 개수
    
    // 인접 리스트 생성
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
      adj.add(new ArrayList<>());
    }
    addEdge(adj, 1, 2); // 1->2
    addEdge(adj, 1, 5);
    addEdge(adj, 2, 3);
    addEdge(adj, 2, 6);
    addEdge(adj, 3, 4);
    addEdge(adj, 4, 7);
    addEdge(adj, 5, 6);

    topologicalSort(n, adj);
  }

  public static void topologicalSort(int n, List<List<Integer>> adj) {
    Queue<Integer> queue = new LinkedList<>();

    // step1: 진입차수가 0인 노드 큐에 넣기
    // 진입차수 계산
    int[] indegree = new int[n+1];  // 0번 노드는 생략하므로 n+1 크기로
    for(int i=1; i<=n; i++) {
      for(int next : adj.get(i)) indegree[next]++;
    }
    // 큐에 넣기
    for(int i=1; i<=n; i++) {
      if(indegree[i]==0) queue.add(i);
    }

    // step2
    while(!queue.isEmpty()) {
      // 큐에서 꺼내기
      int peek = queue.poll();
      System.out.print(peek + " ");
      // 해당 노드에서 나가는 간선 제거
      for(int next : adj.get(peek)) {
        indegree[next]--; // 진입차수 -1
        if(indegree[next]==0)
          // 새롭게 진입차수가 0이 된 노드 큐에 추가
          queue.add(next);
      }
    }
  }

  public static void addEdge(List<List<Integer>> adj, int from, int to) {
    adj.get(from).add(to);
  }
}

 

출력 결과: 1 2 5 3 6 4 7