[17강] 사이클이 없는 방향 그래프 (DAG)

---

안녕하세요 Gliver 입니다.

이번 글에서는 사이클이 없는 방향 그래프 (DAG, Directed Acyclic Graph)에 대해 알아보겠습니다.

 

목차

1. 사이클이 없는 방향 그래프
2. 위상 정렬
3. 정리

 

그래프는 비선형 자료구조이기 때문에 보통 정렬이 불가능하지만 특별한 경우에는 정렬이 가능합니다.

사이클이 없는 방향 그래프일 때 정렬이 가능하며 이때의 정렬을 위상 정렬이라고 합니다.

이번 글에서는 사이클이 없는 방향 그래프(DAG)와 위상 정렬에 대해서 알아보겠습니다.

 

 

사이클이 없는 방향 그래프

사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)는 말 그대로 사이클이 없는 방향 그래프를 의미한다.

사이클이 없는 방향 그래프에서는 정렬이 가능할까?

방향 그래프에서 아래와 같은 상황이 있다면 노드 A가 노드 B보다 앞으로 하여 정렬을 하면 될 것이다.

하지만 방향 그래프라고 해도 아래와 같이 사이클이 생기는 순간 노드 간의 우위를 정의할 수 없게 된다.

따라서, 방향 그래프 중에서 사이클이 없을 때만 정렬이 가능하며 이때의 정렬을 위상 정렬이라고 한다.

 

 

 

위상 정렬

위상 정렬(Topological Sort)은 노드 A에서 노드 B로 가는 간선이 있다면 노드 A를 노드 B보다 앞으로 하여 정렬하는 것을 의미한다.

그리고, 위상 정렬이 가능한 그래프는 사이클이 없는 방향 그래프(DAG)이다.

 

위상 정렬은 왜 하는 것일까?

위상 정렬을 하는 이유는 위상 정렬을 했을 때 문제가 쉬워지는 경우가 많기 때문이다.

위상 정렬이 쓰이는 경우를 예시를 통해서 살펴보자.

다음과 같이 선후수 과목의 정보가 주어졌을 때, 어떠한 과목 순으로 들어야 하는지를 구해보자.
ㆍ과목 B는 과목 A를 들어야 수강할 수 있다.
ㆍ과목 B는 과목 C를 들어야 수강할 수 있다.
ㆍ과목 D는 과목 C를 들어야 수강할 수 있다.

이 상황을 그래프로 나타내면 다음과 같다.

위 그래프는 DAG이므로, 이를 위상 정렬을 하는 것만으로도 어떠한 과목 순으로 들어야 하는지 알 수 있다.
위상 정렬의 결과는 여러 가지 경우가 나올 수 있으며, 위 그래프에 대한 위상 정렬도 다음과 같이 여러 개다.
ㆍA, C, B, D
ㆍA, C, D, B
ㆍC, A, B, D
ㆍC, A, D, B
ㆍC, D, A, B

 

이제 위상 정렬을 구현하는 법에 대해서 살펴보겠다.

만약, 다음과 같은 사이클이 없는 방향 그래프(DAG)가 주어지면 어떻게 위상 정렬을 할 수 있을까?

 

위상 정렬은 노드의 진입 차수를 이용하면 간단하게 구현할 수 있다.

노드의 진입 차수란 해당 노드를 가리키고 있는 간선의 개수를 의미함

그래프에서 진입 차수가 0인 노드부터 방문하며 방문을 한 노드는 자신이 가리키고 있는 노드의 진입 차수를 갱신해 준다.

이를 반복하면 위상 정렬의 순서대로 노드를 방문하게 되며 방문 순서가 위상 정렬의 결과가 된다.

 

위의 그래프에 대해서 위상 정렬을 수행하면 다음과 같은 과정이 순서대로 일어난다.

(각 노드에 파란색으로 표시된 숫자는 현재 해당 노드에 대한 진입차수를 의미한다.)

초기 상태

노드 0을 방문

노드 1을 방문

노드 2를 방문

 

노드 3을 방문

노드 4를 방문

노드 5를 방문

 

위와 같이 위상 정렬을 수행하고 나면 결과는 0, 1, 2, 3, 4, 5 가 나오게 된다.

이를 코드로 구현하는 법은 초기 그래프에서 진입차수가 0인 노드들을 기준으로 방문을 진행하면 된다.

(in_degree는 진입차수를 저장하는 배열, candidate는 초기에 진입차수가 0인 노드를 저장하는 배열, result는 정렬 결과를 저장하는 배열이다.)

 

	#include <bits/stdc++.h>
	using namespace std;
	int N = 6;
	vector<vector<int>> adj_list(N);
	vector<int> in_degree(N, 0);
	vector<int> result;
	void search(int node) {
	if (in_degree[node] > 0) return;
	result.push_back(node);
	for (auto &adj_node : adj_list[node]) {
	in_degree[adj_node] --;
	search(adj_node);
	}
	}
	int main()
	{
	// Create Adjacency List and Update in_degree List
	adj_list[0].push_back(1); in_degree[1] ++;
	adj_list[0].push_back(3); in_degree[3] ++;
	adj_list[1].push_back(2); in_degree[2] ++;
	adj_list[2].push_back(3); in_degree[3] ++;
	adj_list[3].push_back(4); in_degree[4] ++;
	adj_list[3].push_back(5); in_degree[5] ++;
	// Find nodes that Indegree value is 0
	vector<int> candidate;
	for (int node=0; node<N; node++) {
	if (in_degree[node] == 0) candidate.push_back(node);
	}
	// Execute Toplogical Sort
	for (auto &node : candidate) search(node);
	// Print result
	for (auto &node : result) {
	cout << node << ' ';
	}
	return 0;
	}

view raw Topological Sort.cpp hosted with ❤ by GitHub

 

	N = 6
	adj_list = [[] for _ in range(N)]
	in_degree = [0] * N
	result = []
	def search(node):
	if in_degree[node] > 0:
	return
	result.append(node)
	for adj_node in adj_list[node]:
	in_degree[adj_node] -= 1
	search(adj_node)
	# Create Adjacency List and Update in_degree List
	adj_list[0].append(1); in_degree[1] += 1
	adj_list[0].append(3); in_degree[3] += 1
	adj_list[1].append(2); in_degree[2] += 1
	adj_list[2].append(3); in_degree[3] += 1
	adj_list[3].append(4); in_degree[4] += 1
	adj_list[3].append(5); in_degree[5] += 1
	# Find nodes that Indegree value is 0
	candidate = []
	for node in range(N):
	if in_degree[node] == 0:
	candidate.append(node)
	# Execute Toplogical Sort
	for node in candidate:
	search(node)
	# Print result
	print(result)

view raw Topological Sort.py hosted with ❤ by GitHub

 

위상 정렬 알고리즘은 모든 노드와 모든 간선을 한 번씩 살펴보므로 시간 복잡도는 $O(N+M)$이다.

($N$: 노드의 개수, $M$: 간선의 개수)

 

 

 

정리

그래프는 비선형 자료구조이므로 보통은 정렬할 수 없지만 사이클이 없는 방향 그래프(DAG)의 경우 위상 정렬이 가능하다고 하였다.

또, 위상 정렬을 해야 하는 이유는 문제가 더 쉽게 풀릴 수 있기 때문이라고 하였다.

따라서, 상황을 그래프로 표현할 수 있고, 그래프 형태가 사이클이 없는 방향 그래프(DAG)라면 위상 정렬을 고려해 보도록 하자.

 

[관련 문제]

백준 : 줄 세우기 (2252번)

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차: https://gliver.tistory.com/7