위상정렬 (topological sort)

순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘

 

위상정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 사이클이 발생하지 않는 방향 그래프를 의미한다.

즉, 사이클이 발생하는 경우는 위상정렬을 수행할 수 없다.

 

from collections import defaultdict


# edge information

adjacent_list = defaultdict()
adjacent_list['a'] = ['d']
adjacent_list['b'] = ['d']
adjacent_list['c'] = ['e']
adjacent_list['d'] = ['e']
adjacent_list['e'] = []

# 노드의 정보를 visited_list에 저장

visited_list = defaultdict()
visited_list['a'] = False
visited_list['b'] = False
visited_list['c'] = False
visited_list['d'] = False
visited_list['e'] = False

output_stack = []
# 노드를 방문 할때, visited_list의 해당 노드값을 True로 변경, 재방문 불가토록함.
# 방문된 노드의 이웃 노드들을 차례대로 재귀적으로 위상정렬을 수행한다.
# 모든 이웃노드를 방문했을때 현재 노드를 output stack에 저장한다.


def topology_sort(vertex):
    if not visited_list[vertex]:
        visited_list[vertex] = True
        
        for neighbor in adjacency_list[vertex]:
            topology_sort(neighbor)
        output_stack.insert(0, vertex)
        
for v in visited_list:
    topology_sort(v)
    
    
print(output_stack)

# ['c','b','a','d','e']

 

 

시간 복잡도

$ O(V+E) $

 

공간 복잡도

2 dictionaries, 1 list 필요

 

https://www.geeksforgeeks.org/topological-sorting/

Topological Sorting - GeeksforGeeks

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221236874984&proxyReferer=https%3A%2F%2Fwww.google.com%2F

25. 위상 정렬(Topology Sort)

https://www.youtube.com/watch?v=m-Z19d2uS0w