Topological Sort (위상 정렬)

• Topological sort (acyclic graph, adjacency list) - O(V+E)

 

Topological Sort (위상정렬)

 

 

그래프는 정점들을 간선을 통해 모든 관계를 표현한다.

 

 위상 정렬은 그래프에서 정점을 정렬함을 의미한다.

 

 

 

 

위상정렬이 Optimal 을 만족하기 위해서는 

아래 제약조건을 만족해야한다.

 

1. 방향성이 존재 (Directed)

2. Cycle이 존재하지 않아야 한다. (Asyclic)

 

 

 

How to solve ?

 

핵심은 'In degree'가 0인 정점을 출력하는 것.

 

구현은 아래  1 -> 2 패턴을 반복한다.

 

1. In degree가 0인 정점들을 우선 정렬한다.

(In degree  == 0 : 다른 정점의 Dependency가 없기 때문에 출력해도 괜찮은 상태를 의미.)

 

2. In degree를 갱신한다.

(이미 정렬한 정점 관련 Dependency 갱신)

 

 

Data Structure는 Stack이든 Queue든 차이가 없다.

 

 

In degree 가 0인 정점을 우선적으로 채택한다는 단순성에서

Greedy Algorithm으로 분류하고 싶다.

 

 

##########################
###### pseudo code. ######
##########################

def TopologicalSort(graph, V: int) -> List:
""" @param
    graph: adjacency-list. or 2d mat. assumed adjacency-list in this pseudo.
    
           i.e. 
              if you construct graph as adjacency-list -> O(E+V)
              if you construct graph as 2D-Mat -> O(V^2)	

           e.g. graph[0] = [1,2,3] :    3
                                        ^
                                        |
                                        0 -> 1
                                        ↓
                                        2
            

    V: the number of vertexes

"""
    res = [] # sort된 list를 반환한다.
    
    # Edge로부터 Direction을 받는 노드들의 개수를 초기화
    in_degree = [0] * V
    for from, edge in enumerate(graph):
        for to in edge:
            in_degree[to] += 1
    
    visit = [False] * V
    q = Queue() # this can be replaced with 'list', 'stack' ..
    for n in Range(V):
        if in_degree[n] == 0:
            visited[n] = True
            q.push(n)
    
    while !q.empty():
    	cur_node = q.get()
        res.append(cur_node)
        
        for adj_node in graph[cur_node]:
            in_degree[adj_node] -= 1
            if in_degree[adj_node] == 0:
            	q.push(adj_node)
               
    return res