방향 비싸이클 그래프(DAG, Directed Acyclic Graph) 는 보통 작업간의 우선순위를 표현하는 용도로 사용된다고 했다.
그런데 그래프에서 작업들을 어떤 순서로 해야하는지 알아야 하는데 어떻게 할 수 있을까 ?
예를들어 아래와 같은 DAG 가 있고 7부터 작업을 시작한다면 7 다음에 5를 할지 6을 할지 그 순서를 정해야 한다.
이와 같이 일어나야 할 순서에 따라 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬(Topoligical Sort)을 이용할 수 있다.
그림 1)을 위상정렬 하면 그 순서는 7 6 5 4 3 2 1 0로 출력된다.
그럼 실제로 정렬시 작업이 우선순위에 맞는지 즉, 유효한 순서가 되기 위해서 어떤 조건을 만족해야 할까?
당연한 건데 작업의 순서는 왼쪽 → 오른쪽으로 나열되어야 하는 것이다. 왜냐하면 오른쪽에서 왼쪽으로 역방향으로 에지가 있다면 먼저해야할 놈을 나중에 해버리는 꼴이 되버 버리기 때문에 이것은 올바른 작업의 순서가 아니기 때문이다.
그리고 그림2) 처럼 위상정렬은 답이 유일하지 않다.
즉, 위상 정렬은 시작값에 따라 여러 가지로 표현될 수 있고 결론적으로 답이 하나로 유효하지 않다는 것이다.
그럼 위상정렬이 무엇인지 알아보았으니 알고리즘이 어떠한 순서로 진행되는지 구체적으로 살펴보자
위상정렬을 위한 알고리즘은 대표적으로 2가지가 있는데 첫번째는 모든 노드가 제거 될때까지 반복적으로 indegree가 0인 노드를 선택하는 것이다.
에지가 들어가고 나간다는 것과 디그리(degree)는 의미는 노드 V 가 노드 U와 연결되어 있을때 V노드를 기준으로 화살표가 V쪽으로 향하는 것을 incoming edge 라 하고 그 반대를 나가는에지(outgoing egde)라한다.
디그리(degree)는 노드 V의 incoming edge의 모든 수를 incoming degree, 그리고 노드 V에서 나가는 outgoing edge의 수를 outgoing degree라 말한다.
그림 3) 을 기준으로 설명하면 노드 2와 연결된 3 → 2, 1 → 2 에지는 incoming edge 이고 incoming degree는 2개이다.
그리고 노드 1고 연결된 1 → 2, 1 → 3은 outgoing edge 이고 outgoing degree는 2개라고 말한다.
위상정렬이 유효하려면 왼쪽 -> 오른쪽으로 순서가 되어야 한다고 했으니 들어오는 에지가 없다는것은 먼저 선행해야 되는 작업이 없다는 뜻이기 때문이다. 만약 indegree 가 0인 노드가 2개 이상이면 둘중 아무거나 먼저 출력하면 된다.
단계2 - 먼저 출력한 놈은 더이상 볼 필요 없기 때문에 노드를 제거하고 제거후 남은 그래프에서 단계1을 반복한다.
단계3 - 단계 1, 2를 하다가 더이상 노드가 존재하지 않으면 위상정렬이 종료된다.
이제 실제 예제를
그림 4) Kahn's algorithm 예제를 기준으로 코드를 구현하겠다.
step1. 우선 예제를 그래프로 생성해야 하는데 인접리스트로 생성하도록 하겠다.
그래프를 표현하는 코드는 방향그래프(Directed Graph) 구현 에서 사용한 코드를 그대로 사용할 것이다.
|
1
2
3
4
5
6
7
8
9
10
|
Digraph digraph = new Digraph(6);
digraph.addEdge(5, 0);
digraph.addEdge(5, 2);
digraph.addEdge(4, 0);
digraph.addEdge(4, 1);
digraph.addEdge(2, 3);
digraph.addEdge(3, 1);
System.out.println(digraph);
Colored by Color Scripter
|
6 vertices, 6 edges
0:
1:
2: 3
3: 1
4: 0 1
5: 0 2
step2. 노드중에 indegree 가 0인 것들을 찾기위해서 DAG에 있는 각 노드에 대해 indegree (들어오는 가장자리 수)를 계산한다.
Digraph 클래스에는 이미 각 노드마다 indegree 값들이 저장되어 있다. 자세한건 [그래프] 모든 정점의 indegree 계산 를 참고한다.
그리고 indegree 가 0인 정점부터 정렬 되어야 하니 Queue 하나를 생성하여 0 인정점들을 모두 넣는다.
예제 그래프에서는 5 와 4가 indegree =0 이기 때문에 4 , 5 순으로 큐에 들어가게 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.function.Consumer;
public class TopologicalSort {
public void topologicalSort(Digraph digraph, Consumer<Integer> consumer) {
Queue<Integer> queue = new ArrayDeque<>();
int V = digraph.V();
int[] indegrees = digraph.indegrees();
for(int i = 0 ; i < V ; i++) {
if(indegrees[i] == 0) {
queue.add(i);
}
}
}
}
Colored by Color Scripter
|
step3. Queue 에서 indegree = 0 인 정점들을 하나식 꺼낸다.
그리고 꺼낸것은 이미 방문된것이니 출력한다.
그리고 출력된 정점 V 와 인접한 정점들의 에지들을 제거한다.
인접한 정점들의 indegree를 제거한후 그 인접한 정점들의 indegree 가 만약 0 이 되면 queue 에 넣는다.
예제 그래프에서는 4가 큐에서 빠지고 4와 연결된 정점 0과 1의 에지를 제거한다. 하지만 0, 1은 아직도 indegree가 0이 아니므로 큐에 들어가지는 않는다.
다음으로 5가 큐에서 빠지고 5와 연결된 0, 2의 에지를 제거한다. 이제 0, 2가 indegree 가 둘다 0 이므로 2 -> 0 순으로 큐에 들어간다.
step4. 큐가 empt가 될 때 까지 step2, step3을 반복한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.function.Consumer;
public class TopologicalSort {
public static void topologicalSort(Digraph digraph, Consumer<Integer> consumer) {
// indegree 가 0인 것을 queue에 넣는다.
// 먼저 들어온 것이 먼저 나가 출력된다.
Queue<Integer> queue = new ArrayDeque<>();
// 처음 그래프내 indegree 가 0 인것을 queue에 넣는다.
int V = digraph.V();
int[] indegrees = digraph.indegrees();
for(int i = 0 ; i < V ; i++) {
if(indegrees[i] == 0) {
queue.add(i);
}
}
int cnt = 0; // 방문한 정점
while(!queue.isEmpty()) {
// indegree = 0 인 것을 큐에서 꺼내 출력한다.
// 큐에서 꺼낸 정점과 인점한 노드들의 indegree를 하나씩 제거한다.
--indegrees[node];
// 만약 제거된 노드의 indegree = 0 이라면 큐에 추가한다.
if(indegrees[node] == 0) {
queue.add(node);
}
}
cnt++;
}
// 방문된 정점이 원래 정점의 개수와 다르다면 이 그래프는 DAG가 아니다.
if(cnt != V) {
throw new IllegalStateException("There exists a cycle in the graph");
}
}
}
Colored by Color Scripter
|
구현 코드 테스트
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public class KahnsAlgorithmMain {
public static void main(String[] args) {
Digraph g = new Digraph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
// 4 5 2 0 3 1 이 출력된다.
TopologicalSort.topologicalSort(g, (i) ->
System.out.print(i + " "));
}
}
Colored by Color Scripter
|
두번째 위상정렬 알고리즘은 DFS 를 이용하는 방법인데 [그래프] 위상 정렬(Topological Sort) - DFS algorithm 에서 이어서 설명한다.
'알고리즘(Algorithm) > 그래프(Graph)' 카테고리의 다른 글
| [그래프]길찾기 bfs 알고리즘(maze algorithm) (3) | 2019.08.01 |
|---|---|
| [그래프] 그래프에서 사이클 찾는 방법들(Detect Cycle in an Graph) (0) | 2019.07.06 |
| [그래프] 모든 정점의 indegree 계산 (0) | 2019.07.04 |
| 그래프(Graph)-너비우선탐색(BFS, Breadth First Search) algorithm (0) | 2019.07.02 |
| 그래프(Graph)-깊이우선탐색(DFS, Depth First Search) (0) | 2019.07.02 |
