[서울대학교 논자시 준비] 알고리즘 : chapter 10 그래프 : 위상정렬

위상 정렬은 2022년도 1학기 서울대학교 석사 시험에 나왔던 문제이다. 

 

위상정렬 그래프

 

노드 i와 j 사이에 간선 (i, j)가 존재한다면 노드 i는 노드j보다 먼저 수행되어야한다. 모든 간선에 대해서 이 성질만 만족시킨다면 노드 간의 어떤 순서라도 좋다. 이런 성질을 만족하는 정렬을 위상 정렬, topological sort이라고 한다.

 

간선 (i, j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야한다

 

만약 그래프에 사이클이 있다면 이 성질은 결코 만족될 수 없으므로 위상 정렬은 할 수 없다.

 

동작 방식은 아래와 같다.

 

알고리즘 1. 

topologicalSort(G, v){
for i<-1 to n{
	1. 진입 간선이 없는 정점 u를 선택한다
    A[i]=u;
    2. 정점 u와 u의 진출 간선들을 모두 제거한다;
}
// 이 방식으로 하면 배열 A[1 ... n]에는 정점들이 위상정렬되어 있다.
}

위상정렬의 총 수행시간은 O(V+E)이다.

 

알고리즘 2. 

 

다른 위상 정렬 알고리즘을 하나 더 소개한다. 이것은 dfs를 이용한 것으로 앞의 알고리즘보다 더 많이 사용된다. 앞선 알고리즘은 직관적인 접근법을 사용한 것이다.

 

topologicalSort(G)
{
	for each v ( V
    	visited[v]=NO;
    for each v ( V
    	if (visited[v]=NO) then DFS-TS(v);
}

DFS-TS(v)
{
	visited[v]=YES;
    for each x ( L(v) 
    	if (visited[x]=NO) then DFS-TS(x);
}