DAG(Directed Acyclic Graph)와 Topological Ordering(위상정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

DAG(Directed Acyclic Graph)와 Topological Ordering(위상정렬)

DAG(Directed Acyclic Graph)

- DAG는 방향 사이클(directed cycle)이 없는 방향그래프

예 : 작업들의 우선순위

Topological Ordering(위상정렬)

유향 그래프의 Vertex(꼭지점)들의 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해서 위상 정렬을 이용할 수 있다.

정렬의 순서는 유향 그래프의 구조에 따라 여러개의 종류가 나올 수 있다.

위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다.

이 점에서 Directed Acyclic Graph(비순환 유향 그래프)이다.

- DAG에서 노드들의 순서화 V1, V2, ... , Vn.

- 단 모든 에지(Vi, Vj)에 대해서 i<j가 되도록 한다.

위상정렬 알고리즘1 의사코드

TopologicalSort1(G){
	for <- 1 to n {
		진입 간섭이 없는 임의의 정점 u를 선택한다;
		A[i] <- u;
		정점 u와 v의 진출 간선을 모두 제거한다;
	}
	배열 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)

소스 코드(Java)