방향그래프-DAG(Directed Acyclic Graph)

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

ex)작업들의 우선순위

위상정렬(topological ordering)

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

위상정렬 알고리즘1

 topologicalSort1(G)

{

for<-1 to n {

진입간선이 없는 임의의 정점 u를 선택한다;

A[i] <- u;

정점 u와 u의 진출간선을 모두 제거한다;

}

-> 배열 A[1...n]에는 정점들을 위상정렬되어 있다.

}

위상정렬 알고리즘2

topologicalSort2(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);

}