35. topological sort [13 1주차]

35. Topological Sort [13-1주차]

2024년 1월 14일 일요일

오후 5:04

<DAG (Directed Acyclic Graph)>

• Indegree : 방향 그래프에서, 특정 노드에 대해 그 노드로 들어오는 간선의 수
• DAG : 사이클이 없는 방향 그래프. 그래프의 간선 방향이 전체적으로 하나의 흐름을 가지게 된다. 공장의 생산 프로세스를 표현하고 생산 시설의 최적 작동 주기를 계산할 때도 사용된다.

 

DAG은 Indegree가 0인 노드를 하나 이상 갖는다.

• 증명 : 노드가 n개인 DAG의 노드의 Indegree가 모두 0이 아니라고 하자.

v₁ <- v₂ <- … <- v_k-1 <- v_k 와 같이 간선이 연결되어 있을 때, v_k 의 indegree가 0이 아니므로, v_k로 들어가는 간선이 적어도 하나 존재할 것이다. 이 간선이 노드 v_k+1로부터 출발한다고 하면, v_k+1은 v₁, v₂, ..., v_k-1과는 다른 노드여야 한다. 그렇지 않으면 사이클이 생기기 때문이다.

위 내용을 확장하면 v₁ <- v₂ <- … <- v_n과 같이 간선이 연결되어 있음을 알 수 있다. v_n은 indegree가 0이 아니여야 하므로, v₁, v₂, …, v_n-1중 하나로부터 출발하는 간선에 연결되게 된다. 그런데 v₁, v₂, …, v_n-1중 어떤 노드와 연결되든 무조건 사이클이 생기기 때문에 그래프가 DAG이라는 것에 모순이 발생한다.

따라서 DAG에는 indegree가 0인 노드가 적어도 하나 존재해야 한다.

 

 

<Topological sort>

모든 간선이 오른쪽을 향하도록 DAG의 노드들을 정렬하는 것.

 

사이클이 있는 방향 그래프는 Topological Sort가 불가능하다.

• 증명 : 그래프에 사이클이 존재하고, Topological Sort가 완료되었다고 가정한다.

왼쪽 그래프에서 시작하여 오른쪽으로 간선을 따라 이동하다 보면, 이전에 지나간 노드로 되돌아가도록 하는 간선을 만나게 된다. 왜냐하면 사이클이 존재하기 때문이다. 그런데 지나간 노드로 되돌아가기 위해서는 간선이 왼쪽을 향해야 하기 때문에 Topological Sort가 되었다는 것에 모순이다.

 

DAG는 Topological Sort가 항상 가능할까?

이는 알고리즘을 구하면 증명할 수 있다.

 

 

<Topological Sort 알고리즘>

비어 있는 A에 Topological Sort된 결과를 저장할 것이다. 주어진 DAG를 G라고 하면, 알고리즘은 다음과 같이 동작한다.

• G에서 indegree가 0인 노드 v를 A의 끝에 추가한다.
• G에서 v를 제거한다. (연결된 간선들도 G에서 제거)
• v가 제거된 G에 대해 알고리즘을 재귀 호출한다. G가 비어 있으면 재귀 호출을 하지 않는다.

 

재귀 호출이 끝나면, A는 G가 Topological Sort된 형태가 된다.

 

알고리즘 정확성 증명 :

• 각 재귀 호출 과정에서 다음이 유지됨을 증명할 것이다.

• A내에 왼쪽을 향하는 간선은 없다.

 

• 알고리즘 처음 수행 시 :

A에 노드가 하나밖에 하나밖에 없으므로 간선이 존재하지 않는다. 따라서 왼쪽을 향하는 간선도 없다.

• 재귀 호출 시 :

G에서 v의 indegree가 0이고, v를 A끝에 추가시켰을 때 왼쪽을 향하는 간선 v->v' 이 존재한다고 하면, v'은 알고리즘에 추가되기 직전 indegree가 1이상이였을 것이다. G에 간선 v->v' 가 존재했기 때문이다. 이는 알고리즘이 ingreedy가 0인 노드만 추가한다는 것에 모순이다.

따라서 v를 A끝에 추가해도 A에 저장된 노드들 중 왼쪽을 향하는 간선은 존재하지 않는다.

 

G에 indegree=0인 노드를 제거해도, indegree=0인 노드가 항상 남아 있다는 근거 :

DAG에서 어떤 노드를 제거한다고 해서 사이클이 생기지 않는다.

• 증명 : DAG에서 노드 v를 제거해서 사이클 C가 생긴다고 가정한다. v를 다시 추가해도 C가 유지되기에, 원래 DAG였다는 것에 모순이 생긴다. 따라서 DAG에서 어떤 노드를 제거해도 사이클이 생기지 않는다.

따라서 DAG에서 어떤 노드를 제거해도 여전히 DAG이고, indegree=0인 노드가 항상 존재한다.

 

 

<알고리즘 구현 방법>

간선 방향을 무시하고 DFS를 수행해 각 노드의 indegree를 계산할 수 있다. 노드 하나가 제거될 때마다 G의 indegree를 다시 계산해야 하므로 노드 개수만큼 DFS를 실행해야 한다. 따라서 시간복잡도는

 

노드 개수가 N, 간선 개수가 M이라 하면

N*O(N+M) = O(NM)

이 걸린다.

 

 

<Event Queue를 이용한 속도 개선>

1.     먼저 간선의 방향을 무시하고 DFS를 수행해 모든 노드의 indegree를 구한다.

2.     Indegree가 0인 노드들을 queue에 넣는다.

3.     queue에서 노드 x를 뽑아 그래프에서 제외시키고 배열 끝에 넣는다.

4.     x로부터 출발해서 들어가는 간선이 있는 노드들에 대해 indegree를 1 감소시키고, 0이 되는 것은 queue에 넣는다.

5.     3~4를 반복한다.

 

 

맨 처음 DFS를 한번 수행하는데 O(N+M), 노드의 indegree를 업데이트 하는 데 O(M)시간이 걸리므로

전체 시간은 O(N+M) 이다.

 

 

<조금 더 빠르게 하기>

노드를 방문하는 과정에서 간선의 방향을 지키고 DFS를 하면서, 각 노드에 Post Number를 붙인다.

• 방향 그래프에서는 DFS가 끝나고 방문되지 않은 노드가 남을 수 있는데, 이 경우 남은 노드들에 대해 DFS를 다시 실행한다.

 

Post번호 : 특정 노드의 DFS과정이 몇 번째로 끝나는지를 나타내는 수.

 

DAG의 임의의 노드 a와 b에 대해 간선이 a->b와 같이 연결되어 있다면, post번호는 a가 b보다 크다.

증명 :

• DFS에서 a를 먼저 방문하는 경우

DFS에서 간선 a->b를 지난다면, b의 방문이 먼저 끝난다는 것이 자명하다.

간선 a->b를 지나지 않는다면, DFS에서 간선 a->b를 타고 이동할지 판단하는 시점에서 이미 b를 방문했다는 뜻이다. 이 경우에도 b의 방문이 먼저 끝나므로, a의 post번호가 b보다 크다.

 

• DFS에서 b를 먼저 방문하는 경우

b의 방문이 끝나기 전까지 a를 방문할 수 없다. 만약 b의 방문이 끝나기 전에 a에 방문할 수 있다면, b로부터 a까지의 경로가 존재한다는 것이고, 그 경로에 간선 a->b를 더하면 사이클이 되기 때문이다.

b의 방문이 끝난 뒤 a를 방문하므로, a의 post번호가 더 크다.

 

post 번호로 노드를 내림차순 정렬하면 Topological Sort가 끝난다.

DFS과정에서 방문이 끝난 순서대로 배열한 뒤 배열을 뒤집어도 된다.

시간복잡도는 O(N+M)이 걸린다.

 

 

<DAG의 Shortest Path와 Longest Path>

Topological Sort는 출발점 노드로부터 나머지 각 노드로의 shortest path와 longest path를 구하는 데도 사용된다.

DAG를 Topological Sort하고 다익스트라를 수행하면 shortest path 가 구해진다.

단, 다익스트라를 수행할 때, 적힌 숫자(최단 거리 추정값)가 가장 작은 노드가 아니라, 가장 왼쪽에 있는 노드부터 거리를 결정한다.

 

 

 

 

 

일반적인 그래프에서는 음수 가중치가 있으면 다익스트라 알고리즘이 정상적으로 작동하지 않지만, Topological sort된 DAG는 간선의 방향이 정해져 있으므로 음수 가중치가 있어도 정상 작동한다.

 

longest path는 노드에 적히는 숫자를 min이 아닌 max로 업데이트하면 구해진다.