위상 정렬 계산기

위상 정렬 계산기 정보

위상 정렬 계산기는 유향 비순환 그래프 (DAG)의 정점들에 대해, u에서 v로 가는 모든 유향 간선이 있을 때 u가 v보다 앞에 오도록 하는 선형 순서를 계산합니다. 그래프를 간선 리스트나 인접 리스트 형식으로 입력하면, 도구가 Kahn 알고리즘 또는 DFS 포스트 오더를 사용하여 위상 순서를 반환하고, 사이클을 감지(정확한 사이클 경로 포함)하며, 작업을 병렬 실행 레이어로 그룹화하고, 유효한 순서의 개수를 세며, 대화형 그래프에서 각 단계를 애니메이션으로 보여줍니다.

위상 정렬이란 무엇인가요?

유향 그래프 G = (V, E)가 주어졌을 때, 위상 정렬(Topological Sort)은 모든 유향 간선 (u → v)에 대해 u가 v보다 먼저 나타나도록 정점들을 v₁, v₂, …, vₙ과 같이 선형으로 배열하는 것입니다. 위상 정렬은 그래프에 유향 사이클이 없는 경우, 즉 그래프가 DAG인 경우에만 존재합니다. 위상 정렬은 대개 유일하지 않습니다. 여러 정점이 동시에 진입 차수가 0인 경우, 그래프는 여러 개의 유효한 위상 정렬을 가질 수 있습니다.

이 계산기에서 사용되는 알고리즘

Kahn 알고리즘 (BFS 기반, 1962)

Kahn 알고리즘은 가장 직관적인 위상 정렬 방식입니다. 매 단계마다 진입 차수가 0(들어오는 간선이 없는)인 정점을 선택하여 출력에 추가하고, 해당 정점과 그 정점에서 나가는 간선들을 그래프에서 "제거"하며 후속 정점들의 진입 차수를 줄입니다. 진입 차수가 0인 정점이 여러 개인 경우, 최소 힙을 사용하면 사전식으로 가장 작은 순서를 얻을 수 있고, FIFO 큐를 사용하면 입력 순서를 유지할 수 있습니다. Kahn 알고리즘은 O(|V| + |E|) 시간에 실행되며 사이클 감지기 역할도 합니다. 큐가 비었는데 아직 배출되지 않은 정점이 있다면 그래프에 사이클이 있는 것입니다.

DFS 포스트 오더 (Tarjan, 1976)

DFS 알고리즘은 깊이 우선 탐색을 수행하며, 정점의 탐색이 종료될 때(즉, 모든 후속 정점이 완전히 탐색되었을 때) 해당 정점을 스택에 넣습니다. 마지막에 스택을 뒤집으면 유효한 위상 순서가 됩니다. 사이클 감지는 자연스럽게 이루어집니다. 탐색 중 아직 진행 중인 정점(GRAY로 표시됨)을 다시 만난다면 역방향 간선이 발견된 것이므로 그래프는 DAG가 아닙니다. DFS 포스트 오더 역시 O(|V| + |E|) 시간에 실행됩니다.

병렬 실행 레이어

DAG의 레이어 보기는 모든 간선이 낮은 번호의 레벨에서 높은 번호의 레벨로만 향하도록 정점들을 분할합니다. 같은 레이어에 있는 정점들은 서로 독립적이므로 병렬로 실행될 수 있습니다. 레이어의 총 개수는 최장 경로의 길이에 1을 더한 것과 같으며, 이는 무제한의 병렬 처리가 가능하더라도 모든 작업을 마치는 데 필요한 최소한의 순차 라운드 수인 DAG의 임계 경로가 됩니다. 이 계산기는 입력이 DAG일 경우 레이어 보기를 자동으로 생성합니다.

사이클 감지

그래프에 유향 사이클이 포함되어 있으면 위상 정렬이 불가능합니다. 본 계산기는 정확한 사이클 경로(예: A → B → C → A)를 보고하고 시각화 화면에서 사이클 간선을 빨간색으로 강조합니다. 사이클 상의 간선 하나만 제거해도 비순환성을 회복할 수 있습니다.

입력 형식

간선 리스트

각 유향 간선을 출발 -> 도착 형식으로 쓰고, 쉼표나 줄바꿈으로 구분합니다. 허용되는 화살표 변형: ->, →, =>, -->, :. 간선을 체인으로 연결할 수도 있습니다. A -> B -> C는 A->B와 B->C의 줄임표현입니다. 정점 레이블에는 문자, 숫자, 밑줄, 대시, 점을 사용할 수 있습니다.

인접 리스트

각 정점 뒤에 콜론을 쓰고, 해당 정점이 가리키는 직접적인 후속 정점들을 적습니다. 후속 정점이 없는 정점도 D:와 같이 해당 줄을 작성해야 합니다.

계산기 사용 방법

1. 형식 선택: 라디오 버튼을 사용하여 간선 리스트와 인접 리스트 중 하나를 선택합니다.
2. 그래프 입력: 데이터를 붙여넣거나 빠른 예시(옷 입기 순서, 선수 과목, 빌드 대상, 사이클 포함 그래프 등) 중 하나를 클릭합니다.
3. 알고리즘 선택: 고유하고 재현 가능한 순서를 위해 Kahn 사전식 정렬을, 입력 순서를 유지하려면 입력 순서 정렬을, 클래식한 방식을 원하면 DFS 포스트 오더를, 모든 순서를 비교하려면 모두 표시를 선택합니다.
4. "위상 정렬 실행" 클릭: 정렬 순서, 사이클 감지 결과, 레이어 보기, 임계 경로 길이, 총 정렬 가짓수, 대화형 그래프가 아래에 나타납니다.
5. 탐색: 재생 버튼을 눌러 각 정점이 한 번에 하나씩 배출되는 것을 관찰하세요. 진입 차수 배지가 실시간으로 업데이트됩니다. 노드를 드래그하여 레이아웃을 재배치할 수 있습니다.

실제 적용 사례

빌드 시스템 및 컴파일러

make, Bazel, Gradle, npm과 같은 도구들은 빌드 대상을 위상 정렬하여 각 대상이 모든 의존성이 해결된 후에만 컴파일되도록 합니다. 의존성 그래프의 사이클은 대개 치명적인 오류로 보고됩니다.

작업 스케줄링

프로젝트 매니저는 DAG를 사용하여 작업 의존성을 파악합니다. 위상 정렬은 유효한 실행 순서를 제공하며, 레이어 보기는 무제한 병렬 처리 시의 최소 라운드 수를 알려줍니다. 최장 체인은 프로젝트 기간을 결정하는 임계 경로가 됩니다.

교과목 선수 과목 계획

대학 교과목 카탈로그는 DAG입니다. 간선은 선수 과목 관계를 나타냅니다. 위상 정렬 순서는 유효한 학업 계획이며, 레이어는 학생들이 매 학기 병렬로 수강할 수 있는 과목 세트를 알려줍니다.

스프레드시트 재계산

셀 값이 변경되면 스프레드시트는 의존성 순서에 따라 모든 하위 셀을 다시 계산해야 합니다. 이는 셀 의존성 DAG의 위상 정렬입니다. 순환 참조(사이클)는 애플리케이션에서 거부됩니다.

패키지 관리자 및 플러그인 로더

Apt, pip, Homebrew, Maven 및 수많은 플러그인 프레임워크는 의존성 DAG를 위상 정렬하여 설치 또는 로드 순서를 결정합니다.

심볼 분석 및 인퍼런스 스케줄링

컴파일러는 위상 정렬을 사용하여 선언 순서를 정하고, CPU는 데이터 의존성 DAG를 사용하여 데이터 해저드를 위반하지 않고 재배열 버퍼에서 명령어를 스케줄링합니다.

위상 정렬 가짓수 세기

n개의 정점을 가진 DAG에서 서로 다른 유효한 위상 정렬의 수는 1개(완전 정렬된 체인)에서 n!(간선이 없는 그래프)까지 가능합니다. 정확한 가짓수를 계산하는 것은 일반적으로 #P-완전 문제이지만, 정점이 16개 이하인 그래프의 경우 이 계산기는 비트마스크 동적 계획법(f(S) = Σ f(S ∪ {v}), 모든 선행 정점이 S에 포함된 v ∉ S에 대해)을 사용하여 계산합니다.

복잡도 및 성능

• 시간: Kahn 알고리즘과 DFS 포스트 오더 모두 O(|V| + |E|)로, 그래프 크기에 선형 비례합니다.
• 공간: 진입 차수 추적 및 출력 순서를 위해 O(|V|), 인접 구조를 위해 O(|V| + |E|)가 필요합니다.
• 사이클 감지: 두 알고리즘 모두에 내장되어 있습니다. Kahn은 |출력| < |V|일 때 감지하고, DFS는 역방향 간선(GRAY 인접 노드)을 발견할 때 감지합니다.
• 도구의 제한 사항: 대화형 시각화는 최대 80개 정점과 800개 간선까지 지원합니다. 정렬 가짓수 계산은 16개 정점으로 제한됩니다.

자주 묻는 질문

위상 정렬이란 무엇인가요?

유향 비순환 그래프의 위상 정렬은 u에서 v로 가는 모든 유향 간선에 대해 u가 v보다 앞에 오도록 정점을 선형으로 나열하는 것입니다. 이는 의존성을 존중하며 작업을 처리할 수 있는 유효한 순서를 나타냅니다.

이 계산기는 어떤 알고리즘을 사용하나요?

본 계산기는 Kahn 알고리즘과 DFS 포스트 오더를 모두 실행합니다. Kahn 알고리즘은 진입 차수가 0인 정점을 반복적으로 제거하고 그 후속 정점들의 진입 차수를 줄입니다. DFS 포스트 오더는 깊이 우선 탐색을 수행하고 탐색 종료 순서를 뒤집습니다. 둘 다 O(|V| + |E|) 시간에 실행됩니다.

내 그래프에 사이클이 있으면 어떻게 되나요?

유향 사이클이 있는 그래프는 위상 정렬이 존재하지 않습니다. 계산기는 사이클을 감지하여 시각화 화면에 빨간색으로 표시하고, 정확한 사이클 경로를 보고하여 어떤 간선을 제거해야 DAG로 만들 수 있는지 보여줍니다.

사전식으로 가장 작은 위상 순서란 무엇인가요?

여러 위상 정렬이 가능할 때, 매 단계마다 진입 차수가 0인 정점 중 알파벳 순서가 가장 빠른 것을 선택하여 얻는 순서입니다. 이 계산기의 기본 Kahn 모드는 재현 가능하고 안정적인 이 고유 순서를 반환합니다.

레이어 또는 레벨 보기란 무엇인가요?

레이어 보기는 소스 정점으로부터의 최장 경로 길이에 따라 정점을 그룹화합니다. 같은 레이어의 정점은 의존성이 없어 병렬 실행이 가능합니다. 레이어의 수는 최장 의존성 체인 길이에 1을 더한 것과 같으며 최소 병렬 라운드 수를 의미합니다.

그래프가 여러 유효한 위상 정렬을 가질 수 있나요?

네. Kahn 알고리즘 수행 중 어느 단계에서든 진입 차수가 0인 정점이 여러 개라면 그 중 무엇이든 다음에 올 수 있습니다. 이 계산기는 최대 16개 정점까지의 그래프에 대해 정확한 위상 정렬 가짓수를 계산합니다.

Kahn 알고리즘과 DFS 포스트 오더의 차이점은 무엇인가요?

Kahn은 탑다운 방식입니다. 소스(진입 차수 0)를 반복적으로 찾아 먼저 배출합니다. DFS 포스트 오더는 바텀업 방식입니다. 싱크를 먼저 끝내고 순서의 앞에 추가합니다. 둘 다 O(|V| + |E|)이며 유효한 정렬을 생성하지만 대개 결과는 다릅니다. Kahn은 병렬화와 사전식 순서 적용이 쉽고, DFS는 강결합 컴포넌트(SCC) 분석 등 다른 DFS 기반 분석과 결합하기 좋습니다.

이 도구가 지원하는 최대 그래프 크기는 얼마인가요?

이 계산기는 최대 80개 정점과 800개 간선을 지원합니다. 위상 정렬의 총 개수를 세는 기능은 #P-완전 문제이며 상태 공간이 2ⁿ으로 증가하기 때문에 16개 정점으로 제한됩니다. 대화형 시각화 및 알고리즘 애니메이션은 전체 크기까지 매끄럽게 작동합니다.

더 읽어보기

• Topological sorting — Wikipedia
• Directed acyclic graph — Wikipedia
• Depth-first search — Wikipedia
• Critical path method — Wikipedia
• Strongly connected component — Wikipedia