DAG와 위상 순서

DAG (Directed Acyclic Graph)

Directed Acyclic Graph

- DAG는 방향 사이클 (directed cycle)이 없는 방향 그래프이다.

- 유효한 순서의 그래프가 되려면 그래프 상의 엣지들의 방향이 항상 왼쪽에서 오른쪽의 방향으로 진행되어야 한다.

- ex) 작업들의 우선 순위 등

    

위상 정렬 (topological ordering)

- DAG에서 노드들의 순서 $v_1$, $v_2$, ... , $v_n$ (단, 모든 엣지 ($v_i$, $v_j$)에 대해 i < j가 되어야 한다.)

- indegree : 노드를 기준으로 들어오는 엣지의 개수, outdegree : 나오는 엣지의 개수, incoming : 들어오는 엣지, outgoing : 나가는 엣지

첫 번째 위상 정렬에서 모든 그래프에 대해 indegree가 0인 노드를 찾는다. 이는 곧 선행 작업이 존재하지 않는 노드라는 것을 뜻한다. 해당 노드를 찾으면 출력 후 그 노드를 제거한다. 그 후 다시 그래프에 대해 indegree가 0인 노드를 찾아 작업을 반복한다.

위상 정렬 알고리즘

- 슈도 코드

topologicalSort1 (G) {

for 1 to n {

// 이를 위해서 indegree를 알아내는 과정이 선행되어야 한다. 적어도 indegree가 0인지의 여부는 알아야 한다.

진입 간선(incoming)이 없는 임의의 정점 u 선택;

A[i] <- u;

정점 u와 u의 진출 간선(outgoing)을 모두 제거;

}

}

-> 위 코드를 수행하고 나면 A[1 ~ n]에는 정점들이 위상 정렬된다.

-> 수행 시간은 Θ(n + m)

- 진행 과정

위상 정렬 알고리즘2

- 슈도 코드

topologicalSort2 (G) {

for each v ∈ V

visited[v] = false;

make an empty linked list R;

for each v ∈ V // 정점의 순서는 무관하다.

if (visited[v] == false)

DFS-TS (v, R);

}

DFS-TS (v, R) {

visited[v] = true;

for each x adjacent to v

if (visited[x] == false)

DFS-TS(x, R);

//반복문을 빠져나왔다는 것은 기준 노드에서 갈 수 있는 노드를 전부 가보고

//이전 노드로 돌아갈 시점이 왔다는 것을 의미한다.

add v at the front of the linked list R;

}

-> 프로그램이 끝나면 연결 리스트 R에는 정점들이 위상 정렬된 순서대로 저장된다.

-> 수행 시간은 Θ(n + m)

- 진행 과정

수프 넣기를 첫 시작 노드로 설정하였을 때