신비한 개발사전

위상 정렬은 그래프 형식의 데이터를 탐색할 때 사용할 수 있는 알고리즘이다. 모든 그래프 형식에 사용할 수 있는 알고리즘은 아니다. 방향성이 있고, 순환 구조를 이루는 edge가 없는 그래프만 위상 정렬이 가능하다. 이 두가지 특정 조건을 가진 그래프를 directed acyclic graph(dag)라고 한다. Edge로 이어진 노드들 중 다른 노드를 먼저 거쳐야 도달할 수 있는 노드는 의존성(dependency)을 가진다고 표현한다. 위상 정렬에서는 의존성이 없는 노드를 먼저 탐색하는데, 이때 탐색한 노드는 그래프에서 제거해나간다. 따라서 dag 그래프에서는 노드가 제거될 수록 남은 노드들이 가지는 의존성도 줄어든다. 위와 같은 이유로, 만약 순환되는 구조를 가진 그래프라면 각 노드의 의존성의 유무를..