위키득계정 ↗
기술

위상 정렬과 순환 검사

위상 정렬과 순환 검사기술
대상
방향 비순환 그래프
순서 조건
간선의 시작 정점이 끝 정점보다 앞섬
실패 조건
방향 순환
주요 용도
작업과 빌드의 선행 의존성
위상 정렬은 방향 그래프의 모든 선행 제약을 지키도록 정점들을 나열하는 방법이다. 방향 순환이 있으면 전체를 만족하는 순서는 만들 수 없으며 가능한 순서가 하나로 정해지는 것도 아니다.

작업의 선행 관계

자료를 만든 뒤 가공하고 가공한 뒤 발행해야 한다면 각 작업 사이에 방향 있는 제약을 둘 수 있다. 위상 정렬은 이런 제약을 어기지 않는 나열을 찾는다. 선행 관계가 없는 작업들은 순서가 달라도 될 수 있다. 하나의 결과를 얻었다고 그 순서만 유일하게 올바르다고 판단하지 않는다.

순환이 생긴 경우

A를 하려면 B가 필요하고 B를 하려면 C, C를 하려면 A가 필요하다면 어느 작업도 먼저 완료할 수 없다. 이런 방향 순환이 있으면 모든 제약을 만족하는 전체 위상 순서는 존재하지 않는다. 단순히 정렬 알고리즘의 성능을 높여 해결할 문제가 아니라 의존 관계의 모순을 찾아야 한다.

진입 차수를 이용하기

선행 작업이 남아 있지 않은 정점부터 선택하고 그 정점의 뒤 작업에 남은 선행 수를 줄이는 방식을 사용할 수 있다. 모든 정점을 처리하지 못했는데 새로 선택할 수 있는 정점도 없다면 남은 제약을 검토한다. 구현에서는 처리한 정점 수와 전체 수를 비교해 일부 결과를 전체 성공으로 오해하지 않도록 한다.

준비 상태와 실행 완료

여러 작업이 준비되어 있다고 해서 즉시 모두 완료된 것은 아니다. 실행 시스템에서는 선행 작업이 실제로 끝났을 때 뒤 작업을 풀어야 한다. 작업을 큐에 넣은 시점과 성공적으로 완료한 시점을 섞으면 의존성을 일찍 해제할 수 있다. 순서를 구하는 문제와 작업 상태를 관리하는 문제를 연결해 설계한다.

입력 표현 확인

어떤 라이브러리는 정점별로 다음 작업을 받고 다른 라이브러리는 선행 작업을 받는다. 같은 간선 목록을 반대로 해석하면 결과도 뒤집힌다. 고립 정점과 중복 간선을 어떻게 처리하는지도 확인한다. 작은 선행 관계를 직접 그려 반환 순서가 실제 제약을 지키는지 검증하면 표현 오류를 찾기 쉽다.

관련 문서

알고리즘 / 깊이 우선 탐색 / 너비 우선 탐색