위상 정렬(Topological Sort)은 어떤 그래프에서 사용할 수 있나요?

위상 정렬은 방향 그래프에서 모든 간선 u → v에 대해 u가 v보다 먼저 오도록 정점을 나열하는 알고리즘입니다. 사용할 수 있는 그래프는 사이클이 없는 방향 그래프, 즉 DAG(Directed Acyclic Graph)입니다.

핵심 개념

• 선수 과목, 빌드 순서, 작업 의존성처럼 '먼저 해야 하는 관계'를 표현할 때 사용합니다.
• Kahn 알고리즘은 진입 차수 0인 정점부터 제거하며 순서를 만듭니다.
• DFS 방식은 탐색 완료 시점의 역순으로 위상 순서를 얻습니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

function topologicalSort(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  const indegree = Array(n).fill(0);
  for (const [a, b] of edges) {
    graph[a].push(b);
    indegree[b]++;
  }
  const queue = [];
  indegree.forEach((d, i) => { if (d === 0) queue.push(i); });
  const order = [];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    order.push(node);
    for (const next of graph[node]) {
      if (--indegree[next] === 0) queue.push(next);
    }
  }
  if (order.length !== n) throw new Error('cycle exists');
  return order;
}

실무에서 주의할 점

• 사이클이 있으면 모든 의존성을 만족하는 순서가 존재하지 않습니다.
• 가능한 위상 정렬 결과는 여러 개일 수 있습니다. 유일한 순서를 기대하면 안 됩니다.
• 무방향 그래프에는 위상 정렬 개념을 그대로 적용할 수 없습니다.

실무 적용 가이드

• 패키지 빌드, 마이그레이션 순서, DAG 워크플로 스케줄링에 활용합니다.
• 사이클 감지를 함께 구현해 잘못된 의존성을 빠르게 발견합니다.
• 결과의 결정성이 필요하면 진입 차수 0 후보를 우선순위 큐로 관리합니다.

함께 연결해서 보면 좋은 키워드

Topological Sort, DAG, Dependency, Kahn Algorithm

정리

위상 정렬은 방향 그래프에서 모든 간선 u → v에 대해 u가 v보다 먼저 오도록 정점을 나열하는 알고리즘입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.