알고리즘 패턴: 위상 정렬 (Topological sort)

위상 정렬은 그래프 형식의 데이터를 탐색할 때 사용할 수 있는 알고리즘이다.

 

모든 그래프 형식에 사용할 수 있는 알고리즘은 아니다. 방향성이 있고, 순환 구조를 이루는 edge가 없는 그래프만 위상 정렬이 가능하다. 이 두가지 특정 조건을 가진 그래프를 directed acyclic graph(dag)라고 한다.

dag에 해당하는 그래프와 그렇지 못한 그래프 (출처: WilliamFiset @ YouTube)

 

Edge로 이어진 노드들 중 다른 노드를 먼저 거쳐야 도달할 수 있는 노드는 의존성(dependency)을 가진다고 표현한다. 위상 정렬에서는 의존성이 없는 노드를 먼저 탐색하는데, 이때 탐색한 노드는 그래프에서 제거해나간다. 따라서 dag 그래프에서는 노드가 제거될 수록 남은 노드들이 가지는 의존성도 줄어든다.

 

위와 같은 이유로, 만약 순환되는 구조를 가진 그래프라면 각 노드의 의존성의 유무를 확인하는 단계가 무한으로 반복되기 때문에 위상 정렬을 할 수 없는 것이다. 아래 그림으로 예시를 들면 노드 2는 노드 5에 의존하고, 노드 5는 노드 3에 의존하고, 노드 3은 노드 2에 의존하고... 의존하는 구조가 루프를 이루고 있어서 의존성이 없는 노드를 찾을 수 없다.

서로에 의존하는 순환형 구조에서는 의존성이 없는 최상위 노드가 존재하지 않는다 (출처: WilliamFiset @ YouTube)

 

위상 정렬의 탐색 프로세스

위상 정렬에서 그래프를 탐색할 땐 먼저 각 노드가 얼마만큼의 의존성을 가지고 있는지 정리한다. 타겟 노드를 향하고 있는 edge의 갯수를 in-degree라고 하는데, 어떤 노드에도 의존하지 않을 경우 in-degree 값은 0이 된다. 위상 정렬에서는 in-degree가 0인 노드를 queue에 저장해두고, queue에서 순서대로 노드를 꺼내 별도의 배열에 정렬해가는 과정을 반복한다.

출처: WilliamFiset @ YouTube

 

Queue에 저장된 노드를 dequeue해서 정렬 배열에 추가하는 매 iteration마다 노드를 그래프에서 제외하면서 해당 노드에 의존하고 있던 노드들의 in-degree 값을 1씩 차감해준다. 이때, 제거된 노드가 유일한 의존성이었던 노드는 in-degree 값이 0이 될 것이고, 그 노드는 새롭게 queue에 들어가게 된다.

 

한 iteration에 in-degree 값이 0인 노드가 여러개일 수 있다. 위상 정렬에서는 동일한 in-degree를 가진 노드들 사이에서의 탐색 순서가 중요하지 않기 때문에 정렬 패턴이 여러개일 수 있다. 다만 다양한 정렬 방식이 나올 수는 있어도, A → B 순서는 반드시 A → B 순서를 지킨다는 공통된 특징을 가진다.