14-4강. DAG와 위상순서

DAG (Directed Acyclic Graph)

: 방향 사이클(directed cycle)이 없는 방향 그래프.

(자기 자신으로 돌아오지 않는 방향그래프..)

예) 작업들의 우선순위

 

DAG의 예

위의 그래프에서 b가 되기 위해서는 a가 반드시 선행되어야 한다!

 

 

위상정렬 (topological ordering)

- DAG에서 노드들의 순서화(sorting) .. v1, v2, ..., vn.

단 모든 에지(vi, vj)에 대해서 i < j가 되도록!

 

위상정렬의 예

위의 그래프에서 위상정렬을 했을 때, 왼쪽에서 오른쪽 방향으로 정렬했을 때, a-g-... 또는 a-b-... 인데, 역방향으로 가면 안 된다. (오른쪽에서 왼쪽으로 가면 절대 안 된다.)

 

 

어떤 노드에 대해서 들어오는 노드의 갯수를 in-degree, 나가는 노드의 갯수를 out-degree라 한다.

예) 노드 a는 in-degree 가 0이다. : 노드 a에는 들어 오는 노드들이 없다..

 

 

1. 이 그래프의 모든 노드들에 대한 in-degree가 0인 모든 노드들을 찾는다.

2. 위의 그래프에서 in-degree가 0인 노드는 노드 a와 노드 g이다.

(in-degree가 0이라는 의미는 노드 a와 노드 g에 선행하는 작업이 없다는 뜻! 노드 a를 먼저 하든 노드 g를 먼저 하든 상관이 없다..)

3. 노드 a의 in-degree 는 0이다.

4. 노드 a에서 나가는 노드의 갯수인 out-degree는 노드 b와 노드 d로 2개이다.

5. 노드 b와 노드 d를 출력하고, 노드 a에 대한 out-degree 두 개를 지운다.

6. 이 그래프에서 in-degree가 0인 노드를 모두 찾는다.

(이제 노드 g를 먼저 하든 노드 b를 먼저 하든 상관 없다.)

7. 노드 g의 in-degree는 0이다.

8. 노드 g에서 나가는 노드의 갯수인 out-degree는 노드 d로 1개이다.

9. 노드 b의 in-degree는 0이다. (노드 a의 out-degree를 삭제했으니)

10. 노드 b에 대한 out-degree는 노드 c와 노드 e로, 2이다.

... 반복

 

 

// 위상정렬 알고리즘 sudo code 1
topologicalSort1 (G)
{
	for <- 1 to n	// n개의 노드를 출력하면 되니까
    {
    	진입간선(Ingoing degree)이 없는 임의의 정점 u를 선택한다;
        A[i] <- u;
        정점 u와 u의 진출간선(Outgoing degree)을 모두 제거한다;
    }
    > 배열 A[1...n]에는 정점들을 위상정렬되어 있다
}

위의 sudo code에서 1) indegree = 0인 노드가 존재하지 않으면 어떡하지?

 

 

위상정렬 알고리즘 sudo code 2

DFS-TS(v: 노드, R: 연결리스트)

 

 

 

 

 

 

www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4108?tab=curriculum

영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런