그래프 알고리즘 - 4

DAG(Direct Acyclic Graph)

- DAG는 방향 사이클이 없는 방향 그래프

- 예 : 작업들의 우선순위

- DAG에서 노드들의 순서화 v1,v2,v3,....vn, 단, 모든 에지(vi,vj)에 대해서 i<j가 되도록.

indegree : 들어오는 개수

outdegree : 나가는 개수

=> indegree = 0 : 들어오는 개수가 없다.

 

위상정렬 알고리즘 1

문제

- indegree가 0인 노드를 찾기 위해서 모든 노드의 indegree를 알아야 한다.

- 진출간선을 제거했을 때 어떤 방법으로 구현할 것인지 어려움

 

위상정렬 알고리즘2

- dfs-ts는 보통의 깊이 우선탐색이랑 같지만 마지막 줄이 추가됨

- 처음에 마지막으로 도달한 노드는 outdegree가 없다

- 위상정렬 1에서는 가장 먼저 나오는 노드를 찾는 알고리즘이라면

- 위상정렬 2에서는 가장 마지막에 나오는 노드를 찾는 알고리즘이라고 할 수 있다.

 

* 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.