위상 정렬

소프트웨어를 설치하거나, 프로그램을 빌드하거나, 프로젝트를 계획할 때마다 무엇을 먼저 할지 정해야 합니다. 작업 B에 작업 A가 필요하다면 A가 먼저 와야 합니다. 위상 정렬은 이런 규칙들이 얽힌 그물을 한 줄로 바꿉니다.

단방향 화살표로 이어진 노드들의 그래프. 배치된 노드는 초록색이고, 지금까지의 순서가 아래에 한 줄로 그려져 있다
단방향 화살표로 이어진 노드들의 그래프. 배치된 노드는 초록색이고, 지금까지의 순서가 아래에 한 줄로 그려져 있다

아이디어

각 작업을 노드로, "A가 B보다 먼저"라는 각 규칙을 A에서 B로 가는 화살표로 그립니다. 위상 순서는 모든 화살표가 오른쪽을 향하도록 모든 노드를 한 줄로 놓은 것입니다. 무언가를 순서대로 놓기 때문에 정렬이라고 부르지만, 수를 정렬할 때와 달리 화살표만 지키면 됩니다. 화살표의 사슬로 이어지지 않은 노드들은 어느 순서로 와도 됩니다.

불가능할 때

화살표가 사이클을 이루면, 예를 들어 A가 B보다 먼저, B가 C보다 먼저, C가 A보다 먼저라면, A는 자기 자신보다 먼저 와야 합니다. 그래서 위상 순서는 그래프에 방향 사이클이 없을 때만 존재합니다. 이런 그래프를 방향 비순환 그래프(DAG)라고 합니다. 아래 두 방법은 모두 사이클이 있으면 찾아내므로, 사이클 검사로도 쓸모가 있습니다.

예제

화살표 A → C, B → C, B → D, C → E, D → E를 생각해 봅시다. 칸 알고리즘은 들어오는 화살표를 셉니다. A와 B에는 하나도 없으므로 A가 먼저, 그다음 B가 옵니다. B의 화살표를 지우면 C와 D가 준비되어 뒤따르고, 그다음 E가 옵니다. 순서는 A, B, C, D, E입니다. DFS 방식은 A, 그다음 C, 그다음 E를 방문합니다. E가 먼저 끝나고, 그다음 C, 그다음 A가 끝나며, 각각 맨 앞으로 갑니다. 그런 다음 B와 D를 방문하는데, 이들은 끝나서 그 앞에 놓입니다. 순서는 B, D, A, C, E입니다. 두 순서 모두 맞습니다.

칸이냐 DFS냐

1962년 Arthur Kahn이 발표한 칸 알고리즘은 앞에서부터 진행합니다. 지금 시작할 수 있는 작업을 항상 알기 때문에 스케줄링에 알맞고, 준비된 작업 중에서 알파벳 순서 같은 어떤 규칙으로든 고를 수 있습니다. 1976년 Robert Tarjan이 널리 알린 DFS 방식은 끝에서부터 거꾸로 진행하며 깊이 우선 탐색만 있으면 됩니다. 둘 다 걸리는 시간은 노드 수와 간선 수의 합에 비례해 늘어납니다.

로버트 타잔. 1972–73년 존 홉크로프트와 함께 깊이 우선 탐색이 많은 그래프 문제를 선형 시간에 푼다는 것을 보였고, 그 공로 등으로 1986년 튜링상을 받았다.
로버트 타잔. 1972–73년 존 홉크로프트와 함께 깊이 우선 탐색이 많은 그래프 문제를 선형 시간에 푼다는 것을 보였고, 그 공로 등으로 1986년 튜링상을 받았다.

활용

make 같은 빌드 도구는 어떤 파일이 의존하는 파일을 먼저 컴파일합니다. 패키지 관리자는 의존성 순서대로 라이브러리를 설치합니다. 스프레드시트는 셀의 수식이 쓰는 셀을 먼저 계산한 뒤 그 셀을 다시 계산합니다. 대학은 선수 과목 조건을 맞출 수 있는지 확인하고, 컴파일러는 명령어 순서를 정하며, 데이터 파이프라인은 입력이 준비된 뒤에 각 단계를 실행합니다. Unix 명령 tsort는 그 자체로 위상 정렬을 합니다.

직접 살펴보기

앱을 열고 단계를 누르세요. 화살표는 어떤 노드가 어떤 노드보다 먼저 와야 하는지 알려 줍니다. 칸 알고리즘에서는 각 노드의 숫자가 남은 들어오는 화살표의 수이고, 준비된 노드는 파란색입니다. DFS 방식에서는 파란색 노드가 방문 중이고 초록색 노드가 배치된 노드입니다. 순서는 그래프 아래의 줄에서 늘어납니다. 사이클 추가를 체크하고 두 방법이 순서가 없다는 것을 알아내는 모습을 지켜보세요.

자주 묻는 질문

여기서 '위상'은 무슨 뜻인가요?

이 이름은 사물의 정확한 모양이 아니라 어떻게 연결되어 있는지를 연구하는 위상수학에서 왔습니다. 순서는 어떤 노드가 화살표로 이어져 있는지에만 달려 있고, 어디에 그려져 있는지와는 상관없습니다.

순서가 없을 때 사이클은 어떻게 찾나요?

DFS 방식은 바로 보여 줍니다. 아직 방문 중인 노드로 가는 간선과 방문 중인 노드들의 경로를 합친 것이 사이클입니다. 칸 알고리즘은 어떤 노드가 막혔는지만 알려 줍니다. 그 노드들 사이에서 탐색하면 사이클을 찾을 수 있습니다.

올바른 순서 중 특정한 하나를 고를 수 있나요?

네. 칸 알고리즘에서 준비된 노드가 여러 개일 때 원하는 것을 고르면 됩니다. 예를 들어 레이블이 가장 작은 노드나 가장 급한 작업입니다. 우선순위 큐를 쓰면 알파벳 순서로 가장 앞서는 순서를 얻습니다.

위상 정렬은 최단 경로에 어떻게 쓰이나요?

방향 비순환 그래프에서는 위상 순서대로 각 노드의 간선을 완화하면, 한 번의 훑기로 시작점에서의 모든 최단 경로를 찾습니다. 음수 간선이 있어도 되며, 다익스트라나 벨만-포드보다 빠릅니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

위상 정렬 해 보기