위상 정렬 알고리즘 변형: 효율적인 의존성 처리

2025-04-03
위상 정렬 알고리즘 변형: 효율적인 의존성 처리

본 문서는 Kahn 알고리즘을 기반으로 개선된 위상 정렬 알고리즘을 제시합니다. 개별 노드 대신 노드를 집합으로 처리하는 것이 특징입니다. 이 알고리즘은 그래프의 루트 집합을 반복적으로 찾아 제거하는 과정을 반복합니다. 제거된 루트 집합의 순서가 위상 순서를 이루며, 같은 루트 집합 내 노드는 독립적이므로 병렬 처리가 가능합니다. 또한, 사이클을 감지하고 완전히 중단하는 대신 부분적인 위상 순서를 반환할 수 있습니다.

개발