위상정렬

정의

순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위한 알고리즘

순서가 있으므로 사이클이 존재하지 않는 방향 그래프(DAG, directed acyclic graph)로 구성할 수 있을 때 사용 가능하다.

모든 노드를 순회하면서 각 노드의 간선을 순차적으로 제거하기 때문에 노드의 수를 V, 간선의 수를 E라 할때 O(V+E)의 시간복잡도를 보인다.

구현 방법

1. 진입차수가 0인 정점(선행되는 작업이 없는 것)부터 큐에 삽입
2. 큐에서 원소를 꺼내면서 모든 간선을 제거
3. 다시 진입 차수가 0인 정점을 큐에 삽입
4. 2-3의 과정을 큐가 빌 때까지 반복

JavaScript로는 아래와 같이 구현할 수 있다.

function topologySort(n, m, node) {

    const answer = [];
    const graph = Array.from(Array(n + 1), () => Array().fill(0));
    const indegrees = Array(n + 1).fill(0);
  
    const queue = [];
  
    for (let [a, b] of node) {
      graph[a].push(b);
      indegrees[b]++;
    }
  
    for (let i = 1; i < n + 1; i++) {
      if (indegrees[i] === 0) queue.push(i);
    }
  
    while (queue.length) {
  
      const el= queue.shift();
      answer.push(el);
  
  
      for (let next of graph[el]) {
        indegrees[next]--;
        if (indegrees[next] === 0) queue.push(next);
      }
  
  
    }
  
    return answer;
  }

알고리즘 문제로 출제된다면?

• “스킬 여러개가 있고 순서를 정하려 하는데 어떤 스킬은 다른 스킬을 배워야지만 배울 수 있다.” 와 같이 순서를 정하되, 선행, 후행이 있도록 출제됨
• 주의할 점은 위상정렬의 결과는 여러개가 될 수 있으므로 문제에서 “번호가 가장 작은 것부터”와 같은 조건을 주면 우선순위 큐를 이용해 위상정렬을 구현해야 한다.