Topological Sort(위상 정렬) 정리

(참고)

en.wikipedia.org/wiki/Topological_sorting

Topological sorting - Wikipedia

 

컴퓨터 과학에서 방향이 있는 그래프의 위상 정렬이란 그래프의 노드를 정렬한 것으로, 모든 간선 uv에 대해 u는 v 이전,에, v는 u 이후에 배치합니다. 예를 들어, 그래프의 정점들이 TodoList를 나타낼 때, 간선들은 어떤 Todo 이전에 수행해야 할 필수 Todo를 나타냅니다. 위상 정렬은 그래프에서 방향이 있는 사이클이 없을 경우에서만 가능합니다. DAG(directed acyclic graph)라고 불리는 그래프는 적어도 하나 이상의 위상 정렬을 가지고, 선형 시간복잡도를 가집니다. 

 

위상 정렬에서 쓰이는 알고리즘은 대체로 O(|V| + |E|)의 시간복잡도를 가집니다.

 

Kahn's algorithm

Kahn 알고리즘은 최종 정렬된 결과와 같은 순서로 정점을 선택합니다.

첫째로, 시작 노드의 배열을 만들어 집합으로 넣습니다. 이때 시작 노드는 각 노드로 들어오는 간선이 없습니다. 비지 않은 DAG는 반드시 하나 이상의 시작 노드를 가집니다.

L = [] # 정렬된 요소들을 넣을 빈 리스트
S = set([]) # 모든 시작 노드의 집합

# S에 초기값으로 시작 노드들을 넣었다고 가정
while len(S) != 0:
	n = list(S).pop(0) # 시작 노드 집합에서 하나 빼기
    L.append(n) # 정렬 리스트에 넣기
    for e in edge:
    	if n == e[0]: # 해당 노드에서 출발하는 간선일 경우
        	del edge[edge.index(e)] # 간선 제거
            # e[1]로 향하는 간선이 없을 경우 (pseudo if)
            	S.append(e[1]) # 시작 노드에 넣기
if len(edge) != 0:
	return error # 간선이 모두 제거되지 않으면 사이클이 있다고 판단
else:
	return L # 위상적으로 정렬된 리스트 반환

정렬에서 같은 값은 구분되지 않는다는 것을 반영하여 S는 집합 또는 큐나 스택으로 구현할 수 있습니다. 집합 S에서 삭제되는 노드들의 순서에 따라 다른 결과값이 만들어집니다. Kahn 알고리즘의 변형은 병렬 스케줄링을 위한  Coffman-Graham algorithm에 중요 요소로 사용됩니다. 

 

Depth-first search

위상정렬의 다른 방법은 DFS를 사용하는 것입니다. 알고리즘은 그래프의 각 노드를 따라 순회합니다. DFS는 방문한 적이 있는 노드를 방문해야 할 때 종료됩니다. 왜냐하면 DFS를 사용한 위상 정렬의 시작 노드는 밖으로 나가는 간선이 없는 말단 노드이기 때문입니다.

L = [] # 정렬된 노드를 저장할 리스트
visit = [0 for i in range(node_num)] # 노드 방문했는지 체크할 리스트
while 0 in visit:
	n = visit.index(0)
    visit_dfs(n, [])

def visit_dfs(n, temp_visit):
	# temp_visit 비었을 경우 초기화
	global visit
    if visit[n] == 1:
    	return # 방문했을 경우 DFS 종료
    if temp_visit[n] == 1:
    	return # 사이클 발생
    temp_visit[n] = 1 # 임시로 방문 체크하기
    for e in edge:
    	if e[0] == n: # n에서 출발하는 간선이 있을 경우
        	visit_dfs(m)
    temp_visit[n] = 0 # 임시 체크 지우기
    visit[n] = 1 # 영구적으로 체크하기
    L.insert(0, n) # L의 앞에 n 붙이기. DFS는 정렬된 값의 역순으로 노드를 방문하기 때문.

각 노드 n은 n의 자손인 노드를 모두 방문하고 나서 L의 앞에 붙여집니다. 자세히 말하자면, 알고리즘이 노드 n을 더할 때, n에 의존하는 모든 노드들이 L에 들어가 있다는 것이 보장됩니다. 왜냐하면 자손 노드들은 n이 들어가기 전에 재귀 호출되기 때문입니다. 

각 간선과 노드들을 한번만 방문하기 때문에, 이 알고리즘은 선형 시간복잡도를 가집니다. 

 

Applications

 

Parallel algorithms

분산 메모리 기기에서 작동되는 병렬 위상 정렬 알고리즘은 Kahn의 알고리즘을 병행합니다. 높은 계층에서 Kahn의 알고리즘은 indegree가 0인 정점을 반복해서 삭제하고, 이를 위상 정렬된 순서로 넣습니다. 삭제된 정점의 밖을 향하는 간선들이 모두 삭제되었기 때문에, indegree가 0인 새로운 정점이 나타납니다. 이 작업은 남은 정점이 없을 때까지 반복됩니다. D가 그래프 G에서 가장 긴 경로라고 했을 때, 이 알고리즘은 D+1번 반복합니다. 각 반복 작업은 병렬로 수행될 수 있어 Parallel algorithms의 아이디어가 됩니다.

 

프로세스 요소 PE에 각 그래프의 부분들이 저장된다고 가정합시다. 각 PE는 0,..,p-1로 이름이 붙여집니다. 각 PE i는 해당 노드 중 indegree가 0인 노드의 집합을 초기화합니다. 따라서 PE 0부터 p-1까지의 그래프들에 대한 집합이 만들어집니다. 각 노드들에게 전역 인덱스를 할당하기 위해, 집합들의 구간합을 계산합니다.

 

최단 거리 구하기

위상 정렬은 weighted DAG에서 최단 거리를 구할 때에도 적용할 수 있습니다. V가 정점의 리스트라고 하고, 위상 정렬되있다고 합시다. 그러면 다음 알고리즘이 정점 s에 대해 다른 노드들까지의 최단 거리를 구해줄 수 있습니다.

1) d가 V와 길이가 같은 리스트라고 합시다. d는 s로부터의 최단 거리를 저장합니다. d[s] = 0, 다른 값은 무한으로 초기화합니다.

2) p가 V와 길이가 같은 리스트라고 합시다. 모든 요소를 nil로 초기화합시다. 각 p[u]는 s에서 u로 가는 최단거리로 저장됐었던 값(predecessor)을 가집니다.

3)

- s에서 출발해 각 노드 u를 순회합니다.

-- u에서 바로 도달할 수 있는 모든 노드를 순회합니다.

-- w가 u에서 v까지의 가중치라고 합시다.

-- d[v] > d[u]+w이면 d[v]를 d[u]+w로, p[v]는 d[v]로 업데이트합니다. 

 

n개의 정점과 m개의 간선을 가진 그래프에서 이 알고리즘은 O(n+m)의 시간복잡도를 가집니다.