DAG(Directed Acyclic Graph)

유향 그래프는 그래프 내의 각 정점간 단방향 간선만을 가지는 그래프입니다. 이러한 단방향 그래프에서 순환(싸이클)이 존재하지 않는 그래를 DAG라고 합니다.

• 사이클이 존재하는 단방향 그래프 → DAG 가 아님

• DAG 예시, 유향 그래프이면서 사이클이 존재하지 않음.

위상 정렬

위상정렬(Topological Sorting)은 단방향 비순환 그래프(DAG, Directed Acyclic Graph)에서 간선의 방향을 거스르지 않으며 각 정점의 방문 순서를 선형으로 결과를 출력하는 알고리즘입니다.

위상정렬은 일반적으로 대학의 선수과목처럼 어떠한 작업을 수행하기 전에 다른 작업을 수행해야하는 구조를 정렬하는데 사용합니다. 즉 진입 간선을 갖는 정점을 탐색하려면, 해당 정점이 갖는 진입 차수 만큼의 간선에서 탐색이 이루어져야합니다.

즉 위와 같은 그래프가 있을 때, 5 번 정점을 탐색하기 위해서는 3 번 정점과 4 번 정점의 탐색이 선행되어야 합니다.

그렇다면 위와 같은 그래프를 위상정렬을 이용해 결과를 출력한다면 다음과 같을 것입니다.

1 -> 2 -> 3 -> 6 -> 4 -> 5 -> 7 -> 8
//같은 레벨의 정점을 탐색하는 순서는 정점 번호 크기가 작은 순.

진입차수가 없는 1 번 정점으로 부터 탐색을 시작하여 각 정점의 진입차수가 0 이 되었을 때

사이클이 존재하면 안되는 이유 ?

앞서 위상정렬은 단방향 비순환 그래프에서만 가능하다고 작성했습니다. 그 이유는 무엇일까요 ?

위와 같은 사이클이 존재하는 그래프에서는 진입차수가 0이 될 수 없는 구간이 존재합니다.

2 번 정점을 탐색하려면 4 번 정점의 탐색이 우선되어야 하고, 3 번 정점은 2 번, 4 번 정점은 3 번의 탐색이 필요합니다.

그러므로 각 정점은 각 정점의 우선순위가 존재하지 않으며 위상정렬을 통해 탐색 순서를 정의할 수 없습니다.

위상 정렬 방법

위상 정렬은 큐와 스택을 이용해 구현할 수 있습니다. 아래의 내용에서는 큐를 이용한 방법에 대해서 설명합니다.

1. 진입 차수 기록

위상 정렬은 각 정점의 진입 차수를 활용하여 정점의 탐색 순서를 정의하는 방법입니다. 이를 위해서 먼저 모든 정점의 진입 차수를 기록합니다.

2. 진입 차수 0인 정점을 큐에 삽입

각 정점을 방문하면서 진입차수가 0이 된 정점을 큐에 삽입합니다. 초기 DAG에서는 반드시 진입차수가 0인 정점이 존재하므로 해당 정점을 먼저 큐에 넣고 시작합니다.

3. 큐에 담긴 정점에 연결된 간선을 제거하여 진입 차수 감소시키기

큐에 담긴 정점은 탐색을 할 수 있는 정점이므로 탐색 처리를 합니다. 이 후 해당 정점에 연결된 모든 간선을 제거하여 연결된 정점의 진입차수를 감소시킵니다.

4. 모든 정점을 탐색하거나, 큐가 비어있을 때까지 반복

2~3번의 과정을 모든 정점을 탐색하거나, 큐가 빌 때까지 반복합니다. 모든 정점을 탐색하기 이 전에 큐가 비어있다면 해당 그래프는 사이클이 존재하는 것입니다.

정렬 해보기

위 그래프를 직접 위상정렬 해봅니다. 먼저 아래와 같이 진입차수를 기록합니다.

• 각 정점의 진입차수

---------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---------------------------------
| 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
---------------------------------

진입차수가 0인 1 번 정점을 큐에 넣고 시작합니다.

이후 큐에 있는 1 번 정점의 간선을 제거하며 1 번 정점을 결과로 출력합니다.

이에 따라 진입차수가 0이 된 2 번 정점을 큐에 넣습니다.

2 번 정점도 간선을 제거하며, 진입차수가 0이 된 3 번, 6 번 정점을 큐에 넣습니다.

3 번과 6 번 정점에 연결된 간선도 제거하고, 진입차수가 0이 된 4 번 간선도 큐에 삽입합니다. 이 때 간선은 제거되었지만 진입차수가 여전히 0이 아닌 5 번 정점과 7 번 정점은 큐에 넣지 않습니다.

4 번 정점의 간선을 제거하고, 5 번 정점과 7 번 정점을 큐에 담습니다. 이후 5 번 정점과 7 번 정점의 탐색을 마치면 아래와 같은 결과를 도출해낼 수 있습니다.

1 -> 2 -> 3 -> 6 -> 4 -> 5 -> 7 -> 8
//같은 레벨의 정점을 탐색하는 순서는 정점 번호 크기가 작은 순.

사이클이 존재하는 그래프

사이클이 존재하는 그래프인 경우 위와 같은 상황에서 더이상 진입차수가 0인 정점이 존재하지 않기 때문에 탐색할 수 없습니다.

이와 같이 위상정렬을 통해 방향성 그래프의 사이클의 존재 유무도 파악할 수 있습니다.