[알고리즘] 위상 정렬

위상 정렬이란?

그래프를 정렬하는 것입니다. 다시 말해, 방향이 있는 그래프에서 노드 전체를 탐색하는 순서를 1차원으로 나열한 것입니다.

위상 정렬을 수행하기 위해서 두 가지 제약 조건이 존재합니다. 첫째는 언급한 것처럼 방향을 가진 그래프여야하고, 둘째는 그래프에 사이클이 없어야합니다. 당연히 사이클이 있다면 그래프의 시작 지점을 특정할 수가 없습니다.

 

위상 정렬 방법

진입 차수를 기준으로 위상정렬을 수행할 수 있습니다. 진입 차수[In-Degree]란, 한 노드로 들어오는 간선의 수입니다. 아래의 그래프를 보시죠.

    

[A] → [B] → [D]

       ↘︎ [C] ↗︎

 

위에 A부터 순서대로 진입 차수는 [0, 1, 1, 2] 입니다.

 

여기서 진입 차수 0의 의미는 가장 먼저 시작하는 노드가 됩니다. 

또한, 아래의 그래프에서 처럼 진입 차수 0이 없는 그래프는 순환하는 그래프이기 때문에, 위상 정렬을 수행할 수 없습니다.

 

       ↙︎  ← ↖︎

[A] → [B] → [D]

       ↘︎ [C] ↗︎

 

위의 특징을 가지고 위상 정렬을 할 수 있습니다

1. 진입 차수를 계산한다.

2. 진입 차수가 0인 노드들을 찾아 Queue에 넣는다.

    (진입 차수가 0인 노드가 없다면 위상정렬 불가능합니다)

3. Queue에서 노드를 꺼내서 해당 노드를 출력하고, 해당 노드에서 출발하는 모든 노드의 진입차수를 1 감소시킨다.

4. 감소시킨 노드의 진입차수가 0이면 Queue에 넣는다.

5. (3-4)를 Queue가 빌 때까지 수행한다.

 

동시에 진입차수가 0인 노드가 여러 개있을 경우, 위상정렬의 결과는 여러 개가 될 수 있습니다.