[Algorithm] 유향 비순환 그래프

유향 비순환 그래프

유향 비순환 그래프(Directed Acyclic Graph, DAG)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 사이클이 없는 유향 그래프이다. 즉, 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련한 간선을 따라가는 방법이 없는 그래프를 의미한다. 또한 사이클이 없는 방향그래프라는 정의를 통해 모든 트리는 DAG임을 알 수 있다. (어떤 그래프가 주어졌을 때 이 그래프가 DAG인지 판단하기 위해서는 사이클의 존재여부를 확인하면 된다.)

 

 

위상 정렬

위상 정렬(Topological Sort)은 모든 방향 모서리 u v에 대해 정점 u가 순서에서 v 앞에 오도록 정점들을 정렬하는 알고리즘이다. 위상정렬은 유향 비순환 그래프(DAG) 위에서만 동작 가능하며, 작업 순서에 의존관계가 있는 상황과 관련된 문제를 푸는데에 아주 유용하다. 예를 들어서 수업 수강 순서와 같은 상황을 가정해보자. 어떤 학생이 H 수업을 들으려면 A, B, D, E 수업을 선행해야 한다. 또한 D 수업을 들으려면 A, B 수업을 선행해야한다. 이 상황에서 각 수업들을 정점으로 하고, 수업들에 대한 선행수업이 있는 경우를 방향을 갖는 간선으로 표현한다. 이렇게 대응되는 유향 비순환 그래프를 의존성 그래프(Dependency Graph)라고 부른다.

 

 

이 의존성 그래프에서 H 과목을 성공적으로 수강하기위한 유효한 순서로는 다음과 같은 것들이 있을 것이다.

A -> B -> D -> E -> H -> C -> F -> J -> I
B -> A -> D -> E -> H -> C -> F -> J -> I
A -> C -> B -> F -> D -> E -> H -> J -> I
A -> C -> B -> F -> D -> E -> J -> I -> H
...

 

이처럼 H 과목을 수강하기 위해 모든 과목들에 대한 적절한 수강순서를 배열하는 문제를 위상 정렬이라 한다. 물론 과목들에 대한 수강순서는 꼭 유일하지는 않으며, 굉장히 다양한 순서들이 동시에 존재할 수 있다. 트리에 대해서도 위상정렬을 생각해볼 수 있는데, 기본적으로 모든 루트를 갖는 트리들은 사이클이 없기 때문에 위상 순서를 갖는다. 단순하게 생각하면 트리의 루트에서부터 BFS 방문순서로 정점을 정렬하면 위상순서가 될 것이다. 이처럼 트리에서의 위상순서는 명확하기 때문에 일반적으로 좀 더 복잡하며 좀 더 일반적인 상황을 표현하는 DAG에서의 위상순서를 생각해보는 것이 좀 더 의미가 있을 것이다.

일반적으로 위상정렬은 O(V + E)의 시간복잡도를 갖는다.

 

 

 

동작과정 및 구현

다음과 같은 DAG 위에서 위상순서를 찾으려면 어떻게 해야할까? DFS 알고리즘을 활용하면 쉽게 해결 가능하다. 그림을 통해 동작과정을 확인해보자. 왼쪽에 있는 call stack은 DFS 알고리즘의 호출스택으로 함수가 재귀적으로 얼마나 호출되었는지 확인할 수 있다. 그리고 하위에 topological ordering은 이 DFS 알고리즘을 통해 만들어지는 위상순서를 표시해준다.

 

아직 방문하지 않은 임의의 정점을 하나 선택한다. 여기서는 H를 선택한다.

 

 

H에서부터 DFS를 통해 더 이상 하위로 탐색이 불가능할 때까지 방문한다. 호출 스택에는 H, J, M 을 방문한 함수들이 쌓여있을 것이다.

 

 

DFS를 통해 이제 백트래킹을 하게 될 것인데, 이 과정에서 ordering 에 방문완료된 정점을 추가한다.

 

 

그 후, L 정점을 방문하고 퇴각하여 방문완료 정점에 추가한다.

 

 

그 이후, J까지 퇴각한 후에는 다시 I를 방문하고 퇴각할 것이다. 그리고 더 이상 탐색할 정점이 없어진 H 정점에서도 퇴각할 것이다.

 

 

이처럼 DFS 한번을 통해 H를 통해 연결된 부분들에 대한 ordering이 추가되었다. 방문 상태 배열을 유지한 상태로 다시 방문하지 않은 임의의 정점을 선택하여 지금까지와 같은 방법으로 탐색한다. 여기에서는 E 정점이 선택된다. E 정점으로 파생된 모든 정점들이 퇴각하면 다음 그림처럼 표시될 것이다.

 

 

그 후, C 정점에 대해서 다시 DFS를 수행하면 다음과 같이 표시된다.

 

 

즉, 모든 정점에 대해 방문 배열을 공유한 상태로 DFS를 수행하고, 수행 과정에서 퇴각할 때 ordering에 방문 정점을 추가하고 마지막에 ordering 배열을 역순 정렬해준다면 위상정렬된 정점순서를 얻을 수 있다. 

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DAG/1-TopologicalSort.cpp

insooneelife/AlgorithmTutorial

 

 

사이클이 있는 경우

만약 그래프에 사이클이 있다면 어떻게 될까? 아래 그래프에서는 3 -> 4 -> 5 -> 3 의 사이클이 존재한다. 이와 같은 경우 서로가 서로에게 의존성을 갖기 때문에 위상순서를 정의할 수 없게 된다. 그러므로 사이클이 존재하는 그래프에서 위상정렬은 불가능하다.

 

 

 

DAG에서의 최단경로, 최장경로

단일 정점 최단 경로 문제는 O (V + E) 시간 내에 DAG에서 효율적으로 해결할 수 있는데, 이는 DAG에서의 최단경로는 항상 어떤 위상순서 위에 존재하기 때문이다. 그러므로 위상정렬을 통해 먼저 위상순서에 대한 전처리를 수행하고 그 상태에서 최단경로를 만듦으로서 더 효율적인 알고리즘을 설계할 수 있다. 유명한 단일 정점 최단경로 알고리즘 중 하나인 다익스트라 알고리즘은 O(E x logV)의 시간복잡도를 갖는데, 같은 최단경로를 생성하더라도 DAG 위에서라면 위상정렬을 활용할 수 있고 이보다 더 효율적이게 구현할 수 있다. 또한 이 방법은 간선이 음의 가중치를 갖더라도 훌륭하게 동작한다.

 

 

동작과정 및 구현

위상정렬을 활용하여 어떻게 더 효율적인 최단경로를 얻을 수 있는지 알아보자. 다음과 같은 가중치 DAG가 있다고 가정해보자. 먼저 이 DAG에서 위상정렬을 통해 위상순서를 구한다(Arbitrary topological order). 그리고 시작 단일 정점으로부터 모든 다른 정점으로의 최단거리를 저장할 배열을 정의하고, 배열의 모든 원소 값을 양의 무한대 값으로 초기화한다. 이 예제에서는 A 정점을 시작 정점으로 탐색을 수행할 것이므로 A 정점에 대한 최단거리는 0으로 초기화한다. 

 

 

이 상태에서 위상순서대로 정점을 방문하며 방문된 정점까지의 거리와 연결된 간선의 거리를 합한 갑으로 다음 정점까지의 거리를 갱신한다. 물론 이미 저장된 최단거리 값이 더 작다면 내버려두고, 새로 계산된 값이 더 작은 경우에만 갱신한다. 먼저 A와 연결된 모든 간선들에 대해 이 작업을 수행한다. 최단거리 배열에서 B, C의 값은 각각 3, 6으로 갱신된다.

기존까지의 최단거리 + 간선
arr[A] + edge(A, B) = 0 + 3 = 3 (arr[B]보다 작으므로 갱신)
arr[A] + edge(A, C) = 0 + 6 = 6 (arr[C]보다 작으므로 갱신)

 

 

그 후, 위상순서상 다음 값인 B 정점을 방문하여 똑같이 모든 간선에 대해 최단거리를 갱신한다. D, E의 경우 기존의 최단거리 값이 양의 무한대이므로 값이 각각 7, 14로 갱신될 것이다. 반면 C의 경우 기존의 최단거리는 6인데 새로 계산된 거리가 7이므로 갱신되지 않는다.

기존까지의 최단거리 + 간선
arr[B] + edge(B, C) = 3 + 4 = 7 (arr[C]보다 크므로 갱신되지 않음)
arr[B] + edge(B, D) = 3 + 4 = 7 (arr[D]보다 작으므로 갱신)
arr[B] + edge(B, E) = 3 + 11 = 14 (arr[E]보다 작으므로 갱신)

 

 

이와 같은 방법으로 위상순서 위의 모든 정점을 방문하며 최단거리 배열을 갱신하면 A로부터 모든 정점으로의 최단거리를 구할 수 있다. 또한 따로 역추적 테이블을 만들어서 최단경로를 구할수도 있을 것이다.

 

 

DAG에서의 최장경로

DAG에서의 최단경로는 구할 수 있었다. 하지만 최장경로는 어떨까? 일반적인 그래프에서 최장경로를 구하는 문제는 NP-Hard 문제로 정의되어 있지만, DAG에서의 최장경로는 O(V+E) 시간복잡도로 구현이 가능하다. 방법은 생각보다 간단하다. 먼저 그래프의 모든 가중치 부호를 바꾸고(-1을 곱함) 일반적인 DAG에서의 최단경로 문제를 풀고 난 후에 다시 가중치의 부호를 바꾸어주는 것이다. 다음은 가중치 부호를 바꾼 그래프이다.

가중치의 부호가 바뀐 그래프

그 후 계산된 최단거리의 다시 부호를 바꾸어주면 최장거리를 구할 수 있다.

 

 

소스코드(DAG에서의 최단거리, 최장거리)

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DAG/2-Shortest-Longest-Path-DAG.cpp

insooneelife/AlgorithmTutorial

 

 

이미지 출처 (https://github.com/williamfiset/Algorithms)