인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.
DAG (Directed Acyclic Graph)
-
DAG는 방향 사이클(directed cycle)이 없는 방향 그래프.
-
예: 작업들의 우선순위
위상정렬(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 ]에는 정점들을 위상정렬되어 있다
}
수행시간 : θ( n + m )
예)
위상정렬 알고리즘 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);
}
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;
}
-
알고리즘이 끝나면 연결 리스트 R에는 정점들이 위상정렬된 순서로 매달려 있다.
수행시간 : θ( n + m )
예)
