Topological Sort

위상정렬 (Topological sort) 는 cycle이 없는 방향 그래프(Directed Acyclic Graph,DAG) 에서 정점들을 선형순서(간선의 방향을 거스리지 않도록)로 나열하는 것을 의미하며, 주어진 그래프내에서 여러 개의 위상 정렬 결과가 나올수도 있다.

대표적으로 위상정렬을 이용하는 예로 대학교 선수과목 수강 순서를 정할떄 이용할 수 있다.

위상 정렬 알고리즘의 수행과정은 다음과 같다.

1. 그래프에서 진입 차수가 0 인 정점 v 를 출력하고, v와 연결된 간선을 제거한다.
2. 다시 1번 과정을 거치며, 진입 차수가 0인 정점을 찾는다.

from collections import deque;

adj_list = [[1,3,4],[] ,[0,1] , [6] , [5] , [3,7] ,[7] , [8] , []];
n= len(adj_list); path = [];
## 진입 차수 계산
entry = [0] * n; path = deque();
for i in range(n):
    for j in adj_list[i]:
        entry[j]+=1;
## 진입 차수가 0 인 정점들을 경로에 추가한다. 
for i in range(n):
    if(entry[i] == 0):
        path.append(i);
## 진입 차수가 0 인 정점을 차례로 꺼내어, 연결된 간선의 개수를 감소시키고, 
## 다시 진입 차수가 0인 정점을 경로에 추가한다. 
while path:
    cur = path.popleft();
    print(cur,end="->")
    for i in adj_list[cur]:
        entry[i]-=1;
        if(entry[i] == 0):
            path.append(i);

위의 위상정렬 알고리즘은 순방향 방법으로 수행한것이고, 반대로 진출차수가 0인 정점을 역순으로 출력하는 역방향 방법으로 더 효율적으로 수행가능하다.

def dfs(v):
    visited[v] = True;
    for i in adj_list[v]:
        if not visited[i]:
            dfs(i);
    # 연결된 정점을 모두 방문하면 진출 차수가 0인 것으로 간주 
    s.append(v);
            
if __name__ == "__main__":
    adj_list = [[1],[3,4] ,[0,1] , [6] , [5] , [7] ,[7] , [8] , []];
    N = len(adj_list);
    visited = [False] * N;
    s = [];
    # 모든 정점에 대해서 방문하지 않았다면 dfs수행
    for i in range(N):
        if not visited[i]:
            dfs(i);
    # 진출 차수가 0 인 정점들을 역순으로 출력 
    print(s[::-1]);
            

역순으로 수행하였을떄 위상 정렬의 시간 복잡도는 정점의 개수(N)와 간선의 개수(M) 이라고 하였을 떄 O(N+M)의 시간복잡도를 갖는다.

Reference

• 양성봉 저 - 파이썬과 함께하는 자료구조의 이해 (http://www.yes24.com/Product/Goods/57949931)