위상 정렬

 

위상 정렬: 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록' 순서대로 나열하는 알고리즘

def topology_sort():
    result = []
    q = deque()

    """
    진입 차수가 0인 node를 queue에 삽입
    """
    for i in range(1, v+1):
        if indegree_list[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)

        """
        queue에서 꺼낸 node와 연결된 모든 node 간의 간선을 제거 후
        진입 차수가 0인 node를 queue에 삽입
        """
        for nxt in graph[now]:
            indegree_list[nxt] -= 1
            if indegree_list[nxt] == 0:
                q.append(nxt)

    print(result)