[sql] 위상 그래프

26 Dec 2023

위상 그래프(Topological Sorting)는 방향 그래프(Directed Graph)에서 사이클이 없는 노드들의 순서를 찾는 알고리즘이다. 주로 일련의 작업이 순서대로 수행되어야 하는 상황에서 활용된다.

위상 정렬 알고리즘

위상 정렬 알고리즘은 깊이 우선 탐색(DFS)를 기반으로 한다. 각 노드의 진입 차수(In-degree)를 계산하고, 진입 차수가 0인 노드부터 방문하여 해당 노드를 삭제하고 연결된 간선을 제거하는 과정을 반복한다.

여러 가지 방법이 존재하지만, 일반적으로는 스택(Stack)이나 큐(Queue)를 사용하여 알고리즘을 구현한다.

아래는 위상 정렬을 수행하는 SQL 쿼리의 예시이다.

WITH RECURSIVE topological_order AS (
  SELECT id, 1 AS level
  FROM nodes
  WHERE in_degree = 0
  UNION ALL
  SELECT n.id, level + 1
  FROM nodes n
  JOIN graph_edges e ON n.id = e.to_node
  JOIN topological_order t ON t.id = e.from_node
)
SELECT * FROM topological_order
ORDER BY level;

위 쿼리는 고급 SQL 구문을 사용하며, 실제 사용 환경에 따라 성능이나 효율성을 고려하여 최적화될 필요가 있다.

위상 그래프는 작업 스케줄링, 종속성 관리, 데이터 흐름 분석 등 다양한 분야에서 활용되며, 이를 위한 다양한 알고리즘과 접근 방법이 존재한다.

참고 자료

Skiena, S. S. (2008). The Algorithm Design Manual. Springer Science & Business Media.
석준, 박신영, 정광섭, 장진한, 길상곤. (2012). 가장 빨리 만나는 알고리즘. 한빛미디어.
Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2008). Algorithms. McGraw-Hill.

위상 그래프와 위상 정렬 알고리즘에 대한 자세한 내용은 위 참고 자료를 참고할 수 있습니다.