위상 정렬
1. 개요
1. 개요
위상 정렬은 그래프 이론에서 사용되는 알고리즘으로, 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 순서를 나열하는 것을 의미한다. 이는 작업들 간의 선후관계를 표현할 때 특히 유용하다.
이 알고리즘을 적용하기 위한 핵심 조건은 그래프가 사이클이 존재하지 않는 유향 비순환 그래프(DAG)여야 한다는 점이다. 그래프에 사이클이 존재하면 모든 꼭짓점을 방향을 거스르지 않고 배열하는 것이 불가능하기 때문이다.
위상 정렬은 의존성 해결이 필요한 다양한 분야에서 핵심 도구로 활용된다. 대표적으로 패키지 관리나 빌드 시스템에서 모듈 간 의존 관계를 해결하거나, 대학의 수강 과목 선이수 관계를 정리하는 데 사용된다. 또한 회로 설계나 일정 계획과 같은 작업 스케줄링 문제에도 널리 적용된다.
이를 수행하는 대표적인 알고리즘으로는 각 꼭짓점의 진입차수를 기반으로 하는 Kahn의 알고리즘과 깊이 우선 탐색(DFS)을 이용한 방법이 있다.
2. 정의
2. 정의
위상 정렬은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 순서대로 나열하는 것을 말한다. 즉, 그래프의 모든 방향성 간선 (u → v)에 대하여, 정렬 결과에서 꼭짓점 u가 꼭짓점 v보다 앞에 오도록 배열하는 것이다.
이러한 정렬이 가능하기 위한 필요 조건은 그래프에 사이클이 존재하지 않아야 한다는 것이다. 사이클이 존재하면 선후관계가 모순되어 모든 꼭짓점을 조건에 맞게 나열하는 것이 불가능해진다. 따라서 위상 정렬은 사이클이 없는 유향 그래프, 즉 DAG에 대해서만 정의된다.
위상 정렬의 결과는 일반적으로 유일하지 않다. 하나의 DAG에 대해 조건을 만족하는 여러 가지 서로 다른 정렬 순서가 존재할 수 있다. 이는 여러 작업이 서로 독립적인 선후관계를 가질 때, 그 순서를 바꿔도 무방하기 때문이다.
이 개념은 작업 스케줄링, 의존성 해결, 선이수 과목 계획, 데이터 흐름 분석 등 선후관계가 중요한 다양한 분야에서 폭넓게 응용된다.
3. 알고리즘
3. 알고리즘
3.1. Kahn의 알고리즘
3.1. Kahn의 알고리즘
Kahn의 알고리즘은 진입차수를 기반으로 하는 위상 정렬 알고리즘이다. 이 알고리즘은 진입차수가 0인, 즉 자신에게 들어오는 간선이 없는 모든 정점을 찾아서 결과 목록에 추가하는 방식으로 동작한다. 이러한 정점들을 처리한 후에는 해당 정점에서 나가는 간선들을 그래프에서 제거하여 연결된 다른 정점들의 진입차수를 감소시킨다. 이 과정을 반복하여 모든 정점이 정렬될 때까지 진행한다.
알고리즘의 구체적인 절차는 다음과 같다. 먼저, 모든 정점의 진입차수를 계산한다. 그런 다음 진입차수가 0인 정점들을 큐나 스택과 같은 자료구조에 넣는다. 자료구조에서 정점을 하나 꺼내 위상 정렬 결과에 추가하고, 이 정점에서 연결된 모든 인접 정점들의 진입차수를 1씩 감소시킨다. 이때 어떤 인접 정점의 진입차수가 0이 되면 그 정점도 자료구조에 추가한다. 이 과정을 자료구조가 빌 때까지 반복하며, 최종적으로 모든 정점이 처리되면 위상 정렬이 완성된다.
만약 알고리즘이 종료되었는데 아직 처리되지 않은 정점이 남아 있다면, 이는 그래프에 사이클이 존재한다는 것을 의미한다. 사이클이 있는 유향 그래프에서는 위상 정렬을 정의할 수 없기 때문에 Kahn의 알고리즘은 이를 감지할 수 있다.
이 알고리즘의 시간 복잡도는 정점의 수를 V, 간선의 수를 E라고 할 때 O(V+E)이다. 각 정점과 간선을 정확히 한 번씩만 처리하기 때문에 매우 효율적이다. Kahn의 알고리즘은 직관적이고 구현이 간단하여 빌드 시스템이나 패키지 관리자와 같은 의존성 해결이 필요한 다양한 소프트웨어 공학 분야에서 널리 사용된다.
3.2. DFS 기반 알고리즘
3.2. DFS 기반 알고리즘
DFS 기반 위상 정렬 알고리즘은 깊이 우선 탐색을 활용하여 순서를 결정한다. 이 방법은 그래프의 각 정점에 대해 재귀적으로 탐색을 수행하며, 탐색이 완전히 종료된 정점을 역순으로 기록하는 방식으로 동작한다. 핵심 아이디어는 더 이상 방문할 인접 정점이 없는 정점, 즉 모든 후속 작업이 처리된 정점을 결과 목록의 앞쪽에 추가하는 것이다.
알고리즘의 구체적인 단계는 다음과 같다. 먼저, 모든 정점을 '방문 안 함' 상태로 초기화한다. 임의의 정점에서 DFS를 시작하여, 아직 방문하지 않은 모든 인접 정점을 재귀적으로 방문한다. 특정 정점에 대한 DFS 호출이 완전히 끝났을 때, 해당 정점을 스택이나 결과 리스트의 앞에 푸시한다. 이 과정을 모든 정점에 대해 반복하면, 스택에서 꺼낸 순서 또는 리스트의 순서가 곧 위상 정렬의 한 결과가 된다.
이 알고리즘은 사이클 감지 기능을 자연스럽게 통합할 수 있다는 장점이 있다. DFS 탐색 중 현재 방문 경로에 있는 정점을 다시 만나게 되면, 이는 유향 그래프에 사이클이 존재한다는 증거가 되어 위상 정렬이 불가능함을 알 수 있다. 이를 위해 각 정점의 상태를 '방문 안 함', '방문 중', '방문 완료'로 구분하여 관리한다.
DFS 기반 방법은 인접 리스트로 그래프를 표현할 경우 시간 복잡도는 O(V+E)로, 칸의 알고리즘과 동일하다. 구현이 직관적이고 재귀를 사용하기에 코드가 간결해지는 경우가 많으나, 매우 큰 그래프에서는 재귀 깊이 제한에 주의해야 한다.
4. 특징
4. 특징
위상 정렬은 사이클이 없는 유향 그래프(DAG)에서만 적용 가능한 알고리즘이다. 그래프에 사이클이 존재하면 모든 꼭짓점을 방향을 거스르지 않고 나열하는 것이 불가능하기 때문이다. 이는 작업 간 선후관계에 모순이 있음을 의미한다.
위상 정렬의 결과는 일반적으로 유일하지 않다. 하나의 DAG에 대해 가능한 위상 순서는 여러 개가 존재할 수 있다. 이는 동일한 진입차수를 가진 꼭짓점이 여러 개일 때, 처리 순서가 달라질 수 있기 때문이다.
특징 | 설명 |
|---|---|
필수 조건 | |
결과의 유일성 | 일반적으로 결과 순서가 하나가 아닌 여러 개 존재할 수 있음 |
시간 복잡도 | Kahn의 알고리즘 또는 DFS 기반 알고리즘 모두 O(V+E) (V: 꼭짓점 수, E: 변 수) |
주요 용도 |
위상 정렬의 시간 복잡도는 꼭짓점과 변의 수에 선형 비례하며, 이는 대규모 그래프에서도 효율적으로 동작함을 의미한다. 이러한 특징 덕분에 소프트웨어 공학의 패키지 관리자나 컴파일러의 빌드 자동화 도구 등 다양한 분야에서 핵심적으로 활용된다.
5. 응용 분야
5. 응용 분야
위상 정렬은 작업 간의 선후관계가 명확히 정의된 문제를 해결하는 데 널리 활용된다. 대표적인 응용 분야로는 프로젝트 관리나 일정 계획이 있다. 여러 작업이 있고 특정 작업이 끝나야만 다른 작업을 시작할 수 있을 때, 작업들을 유향 그래프로 모델링한 후 위상 정렬을 수행하면 모든 의존 관계를 만족하는 작업 수행 순서를 얻을 수 있다.
소프트웨어 공학 분야에서는 빌드 시스템이나 패키지 관리자에서 의존성을 해결하는 데 필수적으로 사용된다. 예를 들어, 소프트웨어를 컴파일할 때 일부 라이브러리나 모듈은 다른 모듈에 의존하며, 이러한 의존 관계는 DAG를 형성한다. 위상 정렬을 통해 모든 의존성을 올바른 순서로 만족시키며 전체 소프트웨어를 빌드할 수 있는 순서를 결정한다.
교육 과정 설계에도 적용되며, 대학의 교과과정에서 특정 과목을 수강하기 위해 선수강해야 하는 과목들이 있을 때, 이러한 선이수 관계를 그래프로 표현하고 위상 정렬을 수행하면 학생이 졸업 요건을 충족하기 위해 과목을 수강할 수 있는 순서를 찾을 수 있다.
이 외에도 전자 회로 설계에서 논리 게이트의 평가 순서를 결정하거나, 데이터베이스에서 트랜잭션의 스케줄링, 작업 스케줄러에서의 작업 순서 결정 등 다양한 시스템 설계와 운영체제 관련 문제 해결에 기초 도구로 쓰인다.
6. 구현 예시
6. 구현 예시
위상 정렬의 구현은 주로 Kahn의 알고리즘과 DFS 기반 알고리즘 두 가지 방식을 따른다. 두 방법 모두 유향 그래프가 사이클이 없는 DAG라는 전제가 필요하며, 결과는 일반적으로 하나 이상 존재할 수 있다.
Kahn의 알고리즘은 진입차수를 추적하는 방식으로, 직관적이고 효율적이다. 알고리즘은 먼저 모든 꼭짓점의 진입차수를 계산하고, 진입차수가 0인 꼭짓점들을 큐나 스택에 넣는다. 이후 큐에서 꼭짓점을 하나씩 꺼내 정렬 결과에 추가하고, 이 꼭짓점에서 나가는 간선을 제거하여 연결된 꼭짓점들의 진입차수를 감소시킨다. 감소 결과 진입차수가 0이 된 새로운 꼭짓점들을 다시 큐에 추가하는 과정을 반복한다. 최종적으로 모든 꼭짓점을 방문하지 못했다면 그래프에 사이클이 존재한다는 것을 의미한다.
DFS 기반 알고리즘은 깊이 우선 탐색의 특성을 이용한다. 각 꼭짓점을 방문할 때, 아직 방문하지 않은 모든 인접 꼭짓점에 대해 재귀적으로 DFS를 수행한다. 현재 꼭짓점에 대한 탐색이 완전히 끝난 시점에서, 해당 꼭짓점을 결과 리스트의 앞부분에 추가한다. 이는 의존 관계상 나중에 완료되어야 할 작업이 결과 리스트의 앞쪽에 위치하게 되는 방식으로, 최종 리스트를 역순으로 하면 위상 정렬 순서가 얻어진다. 구현 시 방문 상태를 추적하여 사이클을 감지할 수 있다.
두 알고리즘의 시간 복잡도는 인접 리스트를 사용할 경우 꼭짓점 수 V와 간선 수 E에 대해 O(V+E)로 동일하다. Kahn의 알고리즘은 큐를 사용한 반복적 방식으로 구현하기 쉬운 반면, DFS 방식은 재귀 호출 스택을 사용하여 구현이 간결하다는 차이가 있다.
