[CLRS] [20-4] Topological sort(위상정렬)

1. Topological sort

- 순서에 어긋나지 않도록 주어진 Directed Graph의 모든 Node를 한 번씩 방문하는 방법

ex) 주어진 Directed Graph에서 N1 -> N2 엣지가 존재할 시, N1을 N2보다 먼저 방문해야 함

ex)

- (5 -> 4 -> 2 -> 3 -> 1 -> 0)

 

2. Topological Sort과정

- (진입 차수) = (들어오는 Node의 수)

- 진입 차수가 0인 Node 및 연결된 엣지 모두 제거 (기록)

- 제거 대상 Node가 여러개면 그들 가운데 하나만 제거 

- 모든 Node를 방문할 때 까지 같은 과정 반복

- 제거한 Node의 순서가 Topological Sort한 순서가 된다.

 

3. Code

def topological_sort(graph):
    while graph:
        for i in graph.keys():
            topoloical_check = True
            for j in graph.keys():
                if (i in graph[j]) == True:
                    topoloical_check =False
            if (topoloical_check == True) : 
                print(i)
                del graph[i]
                break

graph = {0 : [],
         1 : [],
         2 : [3],
         3 : [1],
         4 : [0,1],
         5 : [0,2]}

topological_sort(graph)

------------------------------------------------------------
4
5
0
2
3
1