위상 정렬은 노드들의 선후 관계에 따라 노드들을 나열하는 알고리즘이다.

가령, 메인 퀘스트 2를 수행하기 위해서는 서브 퀘스트 1, 2, 3을 수행해야 하고, 서브 퀘스트를 받기 위해서는 메인 퀘스트 1을 수행해야 하는 게임이 있다고 해보자.

위상 정렬의 결과는 [메인 퀘스트 1, 서브 퀘스트 1, 2, 3, 메인 퀘스트 2]가 된다. 서브 퀘스트끼리는 순서가 상관이 없어서 [메인 퀘스트 1, 서브 퀘스트 2, 1, 3, 메인 퀘스트 2]과 같이 결과가 나올 수 있지만 메인 퀘스트 1 - 서브 퀘스트들 - 메인 퀘스트 2의 선후관계는 유지된다.

한편 코드는 프리라이프님 블로그와 sunrise-min정리된 내용을 참고했다. DFS를 이용한 구현은 Willing

DAG (Directed Acyclic Graph)

위상 정렬은 DAG 그래프에서 이루어지는 알고리즘이다.

1. 방향성을 가지고 있으며,
2. 싸이클이 없는
   그래프를 DAG라 한다. 만일 싸이클이 존재한다면 (양방향성을 가지는 경우도 사이클임) 위상 정렬을 수행할 수 없다.

시간 복잡도

위상 정렬의 시간 복잡도는 O(V+E)이다.
만일 인접 리스트가 아닌 '인접 행렬'을 사용하는 경우에 시간 복잡도는 O(V^2)이다.

BFS를 이용한 구현

BFS를 이용해서 구현할 때에는 '진입 차수'를 기준으로 큐에 넣는다. 진입 차수란, 특정한 노드로 들어오는 간선의 갯수를 의미한다.

1. 진입 차수가 0인 노드들을 큐에 넣는다.
2. 큐에서 노드를 하나 꺼내어 해당 노드에서 나가는 간선들을 제거한다. (즉 진출 차수를 0으로 만든다. 이에 따라 해당 노드와 연결된 노드들의 진입차수가 1 감소한다.)
3. 큐가 빌 때1-2를 반복한다.

// 노드의 개수와 간선의 개수를 입력 받기
const v = 6;
const e = 6;

// 모든 노드에 대한 진입차수는 0으로 초기화
const indegree = new Array(v + 1).fill(0);

// 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
const graph = new Array(v + 1).fill().map(() => []);

// 방향 그래프의 모든 간선 정보를 입력 받기
const input = [
  [1, 4],
  [5, 4],
  [4, 3],
  [2, 5],
  [2, 3],
  [6, 2],
];
for (let i = 0; i < e; i++) {
  const [a, b] = input[i];
  graph[a].push(b); // 정점 A에서 B로 이동 가능
  indegree[b] += 1; // 진입 차수를 1 증가
}

// 위상 정렬 함수
function topology_sort() {
  const result = []; // 알고리즘 수행 결과를 담을 배열
  const q = []; // 큐 기능을 위한 배열 사용

  // 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
  for (let i = 1; i <= v; i++) {
    if (indegree[i] === 0) {
      q.push(i);
    }
  }

  // 큐가 빌 때까지 반복
  while (q.length > 0) {
    // 큐에서 원소 꺼내기
    const now = q.shift();
    result.push(now);

    // 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
    for (let i = 0; i < graph[now].length; i++) {
      const next = graph[now][i];
      indegree[next] -= 1;

      // 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
      if (indegree[next] === 0) {
        q.push(next);
      }
    }
  }

  // 위상 정렬을 수행한 결과 출력
  console.log(result.join(" ")); //1 6 2 5 4 3
}

topology_sort();

DFS를 이용한 구현

위상정렬을 별도로 구현하지 않아도,
DFS의 원리를 이용하면 위상 정렬의 결과를 출력할 수 있다.
DFS는 연결된 노드들을 스택에 쌓아나가며, 더 이상 탐색할 노드가 없을 때 POP된다.
'더 이상 탐색할 노드가 없다'라는 것은 진출차수가 0이라는 것을 의미하며, 이는 곧 위상에서의 계급이 높다는 것을 의미한다.
(즉 진입차수가 0이 되는 순서를 기준삼았던 BFS와 달리,
DFS는 누가 먼저 진출차수가 0이 되나를 기준으로 계급을 따진다.
어느 방법을 쓰던 '누가 가장 나중에 진입차수가 0이 되는가'라는 선후관계, 즉 위상은 파악할 수 있다.)

DFS를 재귀적으로 호출한 후,
스택에서 pop된 순서의 역순으로 정렬하면 위상정렬의 결과와 같다.

function topology_sort() {
  // 노드의 개수와 간선의 개수를 입력 받기
  const v = 6;
  const e = 6;

  // 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
  const graph = new Array(v + 1).fill().map(() => []);

  // 방향 그래프의 모든 간선 정보를 입력 받기
  const input = [
    [1, 4],
    [5, 4],
    [4, 3],
    [2, 5],
    [2, 3],
    [6, 2],
  ];
  for (let i = 0; i < e; i++) {
    const [a, b] = input[i];
    graph[a].push(b); // 정점 A에서 B로 이동 가능
  }

  const stack = []; // 스택
  const visited = new Array(v + 1).fill(0); // 방문확인 리스트

  for (let i = 1; i < v + 1; i++) {
    if (visited[i] === 0) {
      dfs(i, stack, visited, graph);
    }
  }
  
  //dfs를 끝마친 순서의 역순으로 출력한다.
  console.log(stack.reverse().join(" ")); //6 2 5 1 4 3
}

function dfs(v, stack, visited, graph) {
  visited[v] = 1;
  for (let i = 0; i < graph[v].length; i++) {
    const next = graph[v][i];
    if (visited[next] === 0) {
      dfs(next, stack, visited, graph);
    }
  }
  stack.push(v); //stack에 dfs를 마친 순서대로 저장한다.
}

topology_sort();

결과값

위상정렬 알고리즘의 출력값은 결과가 여러개 나올 수 있다.
위상정렬 알고리즘은 진입차수만을 기준으로 정렬하며, 이에 따라 진입 차수가 0이라면 순서에 관계없이 선택하기 때문이다.

위의 큐를 이용한 구현과 DFS를 이용한 구현도 서로 결과값이 다르다.
하지만 초기 진입차수가 3나 4가 마지막에 나오는 점은 같다. 3과 4의 초기 진입차수가 2였기 때문이다.

간선 리스트인

  [
    [1, 4],
    [5, 4],
    [4, 3],
    [2, 5],
    [2, 3],
    [6, 2],
  ];

에 대하여 나올 수 있는 위상정렬의 경우는 아래와 같다.

1 2 6 5 4 3
1 6 2 5 4 3
1 6 2 5 3 4
1 2 5 6 4 3
1 2 6 5 3 4
1 2 6 3 5 4
6 1 2 5 4 3
6 2 5 1 4 3
6 2 5 1 3 4
6 2 1 5 4 3
6 2 1 5 3 4
2 1 6 5 4 3
2 6 1 5 4 3
2 6 1 5 3 4

총 14가지의 결과가 나온다.