알고리즘 - 위상 정렬

🌎 위상 정렬 (Topology Sort)

---

위상 정렬이란 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다.

 

보통 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용합니다.

 

한 가지 예를 소개하겠습니다.

 

출처 : 나동빈님 블로그(https://m.blog.naver.com/ndb796)

위의 그래프는 일련의 순서(방향)들이 정해져있으며, 사이클이 존재하지 않습니다.

 

이 그래프에서 대학생 되기부터 졸업하기까지 가는 순서(위상 정렬)를 찾아보면 다음과 같습니다.

 

Case 1

하지만 다음과 같이 도달할 수 있습니다.

 

Case 2

 

이처럼 위상 정렬에서는 항상 유일한 값으로 정렬되지 않습니다.

 

더불어, 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없습니다.

 

 

🎢 진입차수와 진출 차수

---

위상 정렬에 대해 더 자세히 알아보기 전에 두가지 개념을 알고 넘어가야합니다.

 

출처 : https://velog.io/@kimdukbae

 

• 진입 차수 (in-degree) : 자기 자신을 가리키는 간선의 개수
• 진출 차수 (out-degree) : 자기 자신에서 나가는 간선의 개수

 

이 간단한 두가지 개념을 알았다면 이제 위상 정렬의 원리를 이해할 시간입니다.

 

 

🔨 구현

---

위상 정렬은 스택과 큐로 구현할 수 있습니다.

 

아래의 예시로 진행해봅시다.

 

사이클이 없는 방향 그래프(Directed Acyclic Graph)

 

 

우선, 각 노드의 진입 차수를 계산해서 배열에 저장합니다. 그 후, 진입 차수가 0인 노드들을 선택하여 큐에 삽입합니다.

 

출처 : https://freedeveloper.tistory.com/

 

큐에서 하나를 꺼내고, 꺼낸 노드가 가리키는 노드들의 진입 차수를 1씩 빼줍니다. 그 후, 진입 차수가 0이된 노드들을 큐에 삽입합니다.

 

 

위의 과정을 모든 노드들의 진입차수가 0이 될 때 까지 반복합니다.

 

큐에서 빠져나온 순서대로 위상 정렬이 이루어집니다.

결과 : 1 → 2 → 5 → 3 → 6 → 4 → 7

 

만약, 큐에 들어가지 않은 노드가 있다면 사이클이 존재한다는 의미로, 위상 정렬을 사용할 수 없습니다.

 

 

코드로 구현하면 다음과 같습니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Topology {

   static boolean[] visited;
   static ArrayList<Integer>[] graph;

   public static void main(String[] args) {
      int[][] edges = {{1, 2}, {1, 5}, {2, 3}, {2, 6}, {3, 4}, {5, 6}, {6, 4}, {4, 7}, {7, 6}};

      int N = 7;

      graph = new ArrayList[N + 1];

      for (int i = 1; i < graph.length; i++) {
         graph[i] = new ArrayList<>();
      }

      for (int[] edge : edges) {
         graph[edge[0]].add(edge[1]);
      }

      /**
       * 모든 노드가 출력되지 않는다면(큐에 들어가지 않은 노드가 있다면) 사이클이 존재
       */
      System.out.println(Arrays.toString(sort())); // 1, 2, 5, 3, 6, 4, 7
   }

   /**
    * 위상 정렬
    */

   public static int[] sort() {
      int[] inDegree = new int[graph.length];
      int[] answer = new int[graph.length - 1];
      int idx = 0;

      visited = new boolean[graph.length];

      // 진입 차수 저장
      for (int i = 1; i < graph.length; i++) {
         ArrayList<Integer> adj = graph[i];

         for (Integer node : adj) {
            inDegree[node]++;
         }
      }

      // 진입 차수가 0인 노드 찾기
      int start = -1;
      for (int i = 1; i < inDegree.length; i++) {
         if (inDegree[i] == 0) {
            start = i;
            break;
         }
      }

      // 진입 차수가 0이 없다면 사이클이 있음
      if (start == -1) {
         return null;
      }

      Queue<Integer> queue = new LinkedList<>();

      queue.add(start);

      while (!queue.isEmpty()) {
         Integer cur = queue.poll();

         // 진입 차수가 0인 노드이므로 순서 배열에 저장
         answer[idx++] = cur;

         for (Integer next : graph[cur]) {
            // 연결 노드 진입 차수 빼주기
            if (--inDegree[next] == 0) {
               queue.add(next);
            }
         }
      }

      return answer;
   }
}