위상정렬

위상정렬 알고리즘

 

-큐를 이용

1. 진입차수가 0인 모든 노드를 큐에 넣는다. 

2. 큐가 빌 때까지 다음의 과정을 반복한다.

   1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.

   2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 

 

--> 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. 

 

(특징)

- 사이클이 없는 방향그래프(DAG)여야 한다.

- 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답 존재.

- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있음 

 

(시간복잡도)

- 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거하므로 시간복잡도는 O(V+E)이다. 

 

위상정렬 코드  

from collections import defaultdict, deque


def topologicalSort(graph, level,n):
    queue = deque()
    for i in range(1,n+1):
        if level[i] == 0:
            queue.append(i)

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            level[i] -= 1
            if level[i] == 0:
                queue.append(i)


def main():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    level = defaultdict(int)

    for i in range(m):
        a, b = map(int,input().split())
        graph[a].append(b)
        level[b] += 1

    topologicalSort(graph, level,n)


if __name__ == '__main__':
    main()