Topological Sorting: Kahn, DFS와 DAG 의존성 정렬

Topological Sorting은 방향 그래프에서 모든 간선:

Code

u → v

에 대해 u가 v보다 먼저 나오도록 정점을 선형 순서로 배치합니다.

이 순서는 DAG(Directed Acyclic Graph) 에서만 존재합니다.

Kahn 알고리즘

Kahn은 in-degree를 사용합니다.

모든 정점의 in-degree를 계산합니다.
in-degree가 0인 정점을 Queue에 넣습니다.
하나를 꺼내 결과에 추가합니다.
이 정점의 outgoing edge를 제거한 것처럼 이웃의 in-degree를 줄입니다.
새로 0이 된 정점을 Queue에 넣습니다.
모든 정점을 처리하지 못하면 Cycle이 존재합니다.

JavaScript

function topoSort(graph) {
  const nodes = new Set();
  const indegree = new Map();

  for (const [u, list] of Object.entries(graph)) {
    nodes.add(u);
    for (const v of list) nodes.add(v);
  }

  for (const n of nodes) indegree.set(n, 0);

  for (const list of Object.values(graph)) {
    for (const v of list) {
      indegree.set(v, indegree.get(v) + 1);
    }
  }

  const queue = [...nodes].filter(
    n => indegree.get(n) === 0
  );

  let head = 0;
  const order = [];

  while (head < queue.length) {
    const u = queue[head++];
    order.push(u);

    for (const v of graph[u] ?? []) {
      indegree.set(v, indegree.get(v) - 1);

      if (indegree.get(v) === 0) {
        queue.push(v);
      }
    }
  }

  return order.length === nodes.size
    ? order
    : null;
}

DFS 방식

DFS에서 모든 이웃 처리가 끝난 뒤 정점을 결과에 넣고 Finish Order를 뒤집어도 Topological Order를 얻을 수 있습니다.

Cycle Detection을 위해 unvisited, visiting, finished 상태가 필요합니다.

여러 정답

서로 의존하지 않는 Task가 있으면 Topological Order는 여러 개일 수 있습니다.

활용

Build Order
Course Prerequisite
Package Dependency
CI/CD
Workflow
ETL Pipeline
Database Migration
DAG Dynamic Programming

복잡도

Code

O(V + E)

정리

Topological Sorting은 «A가 B보다 먼저 실행되어야 한다»와 같은 의존성을 정렬하는 핵심 알고리즘입니다.

Kahn 알고리즘

Kahn은 in-degree를 사용합니다.

모든 정점의 in-degree를 계산합니다.

in-degree가 0인 정점을 Queue에 넣습니다.

하나를 꺼내 결과에 추가합니다.

이 정점의 outgoing edge를 제거한 것처럼 이웃의 in-degree를 줄입니다.

새로 0이 된 정점을 Queue에 넣습니다.

모든 정점을 처리하지 못하면 Cycle이 존재합니다.

JavaScript

function topoSort(graph) {
  const nodes = new Set();
  const indegree = new Map();

  for (const [u, list] of Object.entries(graph)) {
    nodes.add(u);
    for (const v of list) nodes.add(v);
  }

  for (const n of nodes) indegree.set(n, 0);

  for (const list of Object.values(graph)) {
    for (const v of list) {
      indegree.set(v, indegree.get(v) + 1);
    }
  }

  const queue = [...nodes].filter(
    n => indegree.get(n) === 0
  );

  let head = 0;
  const order = [];

  while (head < queue.length) {
    const u = queue[head++];
    order.push(u);

    for (const v of graph[u] ?? []) {
      indegree.set(v, indegree.get(v) - 1);

      if (indegree.get(v) === 0) {
        queue.push(v);
      }
    }
  }

  return order.length === nodes.size
    ? order
    : null;
}

Topological Sorting: Kahn, DFS와 DAG 의존성 정렬

Kahn 알고리즘

DFS 방식

여러 정답

활용

복잡도

정리

그래프 Connected Components: DFS, BFS와 Union-Find

Articulation Points: Tarjan과 Low-Link로 핵심 정점 찾기

Topological Sorting: Kahn, DFS와 DAG 의존성 정렬

Kahn 알고리즘

DFS 방식

여러 정답

활용

복잡도

정리

그래프 Connected Components: DFS, BFS와 Union-Find

Articulation Points: Tarjan과 Low-Link로 핵심 정점 찾기