8. 기타 그래프 이론: 위상 정렬

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

사이클이 없는 방향그래프(DAG:Direct Acycle Graph) 에서 위상정렬 하는 방법 설명.

 

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

2. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

 

이것을 큐가 빌 때까지 반복한다

 

만약 그래프에 사이클이 존재한다면..

사이클에 포함되는 노드는 진입차수가 모두 1이상이 되므로 큐에 들어가지 못하고 정렬이 끝날것이다

 

from collections import deque

v,e=map(int,input().split())
indegree=[0]*(v+1)
graph=[[]for i in range(v+1)]
for i in range(e):
    a,b=map(int,input().split())
    indegree[b]+=1
    graph[a].append(b)

def topology_sort():
    result=[]
    q=deque()
    for i in range(1,v+1):
        if indegree[i]==0: #들어오는 간선이 없는 노드
            q.append(i)
    while q:
        now=q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i]-=1
            if indegree[i]==0:
                q.append(i)
    for i in result:
        print(i,end=' ')

topology_sort()