방향 비순환 그래프(DAG, Directed Acyclic Graph)

지금까지 그래프(Graph)란 무엇인지 간략하게 살펴보고 인접행렬과 인접리스트를 통해 그래프를 구현해보기도 하였다.
그리고 그래프를 순환(traversal) 하기위해 방향있는 그래프던 없는 그래프던 똑같이 적용할 수 있는 너비우선탐색(BFS, Breadth First Search) 과 깊이우선탐색(DFS, Depth First Search) 알고리즘도 알아보았다.

 

이번 시간에는 DAG(Directed Acyclic Graph)에 대해서 알아볼텐데 DAG란 유향 비순환 그래프 or 유향 비사이클 그래프 or 방향 비순환 그래프 or 방향 비사이클 그래프 or 방향성 비사이클 그래프처럼 다양하게 번역되어지는데 핵심은 그래프 간선(에지)에 방향이 있고

처음 출발한 노드(정점) v에서 시작하여 끝내 다시 v로 돌아가 순환 반복될 수 있는 방법이 없는 그래프라고 이해하면된다.

 

그림(비방향 그래프 vs 방향그래프)은 그래프에서 방향이 없는 것과 있는 것을 보여주는데 방향그래프는 정점마다 연결된 에지에 화살표로 들어오고 나가는 방향에 대해서 표시를 하는 특성을 가진다. 

그림 1 ) 비방향 그래프 vs 방향그래프

그럼 순환과 비순환의 차이는 무엇일까 ? 순환한다는 것은 출발한 노드(정점) v에서 시작하여 끝내 다시 v로 돌아가 순환 반복될수있다고 하였는데 그림2 그래프는 S에서 출발하여 E로 갈수 있는 다양한 간선들이 존재하고 그 간선들에는 방향이 있으므로 방향그래프이다.
하지만 E에서 다시 S로 되돌아갈 에지가 없어 순환 반복될수 없는데 이런 그래프를 비순환 그래프라고 한다.  

그림 2) 비순환 방향 그래프

무방향 과 방향 그래프일 때 순환을 하는 알고리즘에 좀 차이가 있는데 무방향 그래프에서는 DFS나 BFS로 순회할 때 출발점이 속해 있는 커넥티트 컴포넌트(Connected Component) 상에 있는 모든노드를 당연히 다 방문하겠지만 방향 그래프라면 커넥티드 컴포넌트의 개념이 좀 달라지게 된다. 즉, 무방향 그래프라면 어떤 두 노드 S -> E 에서 갈수 있다면 그 역으로 갈수 있기 때문에  커넥티드 컴포넌트의 개념이 명확하게 정의가 되서 무방향 그래프에서 어떤 노드에서 시작을 하더라도 DFS or BFS로 모든 노드를 순회 할 수 있다.

방향그래프에서는 에지에 방향이 있어 좀 복잡해지는데 S -> E로 갈수 있다고해서 꼭 E -> S로 갈수 있다는 보장이 안되기 때문에  DFS나 BFS를 했을때 S 라는 노드에서 출발했을때는 다 방문을 하는데 E에서 출발했을때는 다 방문이 안되는 일이 일어 날 수 있다.

하지만 BFS 나 DFS의 결과에 좀 차이가 있을 뿐 알고리즘 자체는 크게 다르지는 않기 때문에  BFS, DFS가 반드시 무방향그래프에만 적용되는 알고리즘은 아니다.

 

 

DAG가 어떤 특성을 가지는지 알아보았는데 그럼 DAG로 표현할 수 있는 용도는 무엇이 있을까?

일반적으로 DAG는 작업들의 우선순위를 표현을 할 때 DAG를 많이 사용하게 된다.

예를들어 공장에서 작업 스케줄링을 할 때 A 라는 작업이 끝나고 B를 해야하고 B 가 끝난 다음에는 C,D를 해야한다는 것을 DAG로 표현할 수 있다.

그림 3)은 빅 데이타를 처리하다보면 여러 개의 태스크로 나뉘어서 순차적으로 실행할 필요가 있는데 그런 데이터 워크 흐름을 관리할수 있도록 DAG를 사용하고 있는 데이터 워크플로우 도구 중 하나인 Airflow 의 DAG 뷰를 보여주고 있다.

 

그림 3) Airflow DAG 뷰

▲ [출처] https://medium.com/@hafizbadrie/airflow-when-your-dag-is-far-behind-the-schedule-ea11bf02e44c

 

 

따라서 작업간의 순서는 어떤 작업을 하기위해 선행되어야할 작업들이 있고 그런 작업들을 모두 진행되면 최종적으로 작업을 완료할 수 있는데 만약  DGA가 아니고 싸이클이 있는 그래프라면 그 잡업은 영원히 완수되기 어려울 것이다. 

따라서 잡업간의 순서를 그래프로 표현할때는 DAG로 표현하는게 일반적이다.