DAG (Directed Acyclic Graph)
유향 비순환 그래프(directed acyclic graph, DAG, 유향 비사이클 그래프), 방향 비순환 그래프(방향 비사이클 그래프, 방향성 비사이클 그래프)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 방향 순환이 없는 무한 유향 그래프이다. 즉, 무한히 수많은 꼭짓점과 간선으로 구성되며 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련 한 간선을 따라가는 방법이 없다. 다시 말해 DAG는 위상정렬이 있는 유향 그래프이다.
출처: https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%96%A5_%EB%B9%84%EC%88%9C%ED%99%98_%EA%B7%B8%EB%9E%98%ED%94%84
DAG는 방향 사이클(directed cycle)이 없는 방향 그래프
사이클 : 다시 자기 자신으로 돌아오는 경로
예시 : 작업들의 우선순위
예를 들면, 집을 지을 때 기초공사나 기둥세우기, 인테리어 등을 해야한다.
이 때, 기둥을 세우기 전에 인테리어를 할 수 없듯이
다른 것 보다 선행 되어야 하는 것들 표현 하기 위해 DAG가 유용하게 사용된다.
출처: https://new93helloworld.tistory.com/182
위상정렬 (topoligical ordering)
DAG에서 노드들의 순서화 v1, v2, ... vn,
단, 모든 (vi, vj)에 대해서 i<j가 되도록
DAG에서는 우선순위를 표현하기 위해 위상 정렬을 사용한다.
위상 정렬이란, 작업을 실제로 한번에 하나씩 순서대로 처리한다면
어떤 순서로 작업해야 하느냐를 표현한 것이다.
즉, 작업의 순서대로 노드를 일렬로 정렬하는 것이다.
출처: https://new93helloworld.tistory.com/182
위상정렬 알고리즘 1
topoligicalSort1(G){
for <- 1 to n{
진입간선이 없는 임의의 정점 u를 선택한다;
A[i] <- u;
정점 u와 u의 진출간선을 모두 제거한다;
}
> 배열 A[1...n]에는 정점들이 위상정렬 되어있다
}
수행시간 : O(n+m)
위의 코드는 첫번째 위상 정렬 알고리즘이다.
알고리즘을 보기에 앞서 그래프에 대한 용어를 정리하자.
방향 그래프에서 들어오는 엣지를 Incomming 나가는 엣지를 Outgoing이라고 한다.
또한, 들어오는 엣지의 개수를 Indegree 나가는 엣지의 개수를 Outdegree라고 한다.
첫번째 위상 알고리즘은 간단하고 직관적이다.
첫째로, 모든 노드들에 대해서 indegree가 0인 노드를 찾는다.
indegree가 0라는 것은 해당 작업에 선행해야 할 작업이 없다는 것을 뜻한다.
2개 이상 존재하면 그중 하나를 선택한다.
그 후, 노드 A와 A에서 나가는 엣지를 그래프에서 제거한다.
그리고 다시, 남은 그래프에서 indegree가 0인 노드를 찾는다.
작업이 끝났으면 해당 노드와 해당 노드에서 나가는 엣지를 그래프에서 제거한다.
이와같은 작업을 반복하면 결론적으로 마지막 노드까지 도달할수 있으며
모든 노드가 위상 정렬된다.
= 들어오는 엣지의 개수가 0인 것을 찾아서 (indegree가 0인 것을 찾아서)
걔를 처리하고, (제거하고) 남은 그래프에서 또 indegree가 0인 것을 찾아서 제거하는 구조
위상정렬 알고리즘 2
topoligicalSort1(G){
for each v∈V
visited[v] <- NO;
make an empty linked list R;
for each v∈V : 정점의 순서는 상관없음
if(visited[v] = NO) then
DFS-TS(v, R)
}
DFS-TS(v, R){
visited[v] <- YES;
for each x adjacent to v do
if(visited[x] == NO) then
DFS-TS(x,R);
add v at the front of the linked list R;
}
DFS-TS(v, R){
visited[v] <- YES;
for each x adjacent to v do
if(visited[x] == NO) then
DFS-TS(x,R);
add v at the front of the linked list R;
}
두번째 위상 정렬 알고리즘이다.
일단, 모든 노드들에 대해서 visited를 NO로 설정해준다.
아직 아무 노드도 출력 되지 않았다는 뜻이다.
그 후에, 하나의 빈 링크드 리스트 R을 만드는데,
노드를 위상 정렬해서 정렬된 순서대로, 연결 리스트로 노드들을 정렬할 것이기 때문이다.
그리고 아직 방문하지 않은 아무 노드 하나를 잡아서 그 노드에서 출발하는 DFS를 실행한다.
DFS는 방문한 노드를 체크하고 그 노드와 인접한 노드 x에 대해
해당 노드가 방문되지 않았다면 다시 DFS를 실행한다.
그러나 일반적인 DFS와 다른점은 마지막 줄이다.
for 반복문을 빠져 나왔다는 것은 모든 노드를 방문해보고 갈곳이 없을 때 이다.
일반적인 DFS는 뒤로 되돌아 갔으나, 여기서는 링크드 리스트 R에 해당 노드를 추가해준다.
= 알고리즘이 끝나면 연결 리스트 R에는 정점들이 위상정렬된 순서대로 매달려 있다.
댓글
댓글 쓰기