알고리즘 - 기타 그래프 관련 알고리즘 (위상 정렬 알고리즘)

# 사이클이 없는 방향 그래프에서 방향성을 거스르지 않도록순서대로 나열하는 것을 의미하고 이의 대표적인 경우는 선수과목을 고려한 학습 순서가 있다. 

 

# 사이클이 있으면 진입차수가 1이상이 되기 때문에 큐에 들어갈 수 없어서 수행이 불가하다.

 

 

# 진입차수가 0이 될 때 큐에 삽입해서 다음 노드를 확인해주는 방식으로 실행

# 여러 답이 존재한다고 보는 이유는 위에 예시에서는 1 - > 2 -> 5 순서로 간 이유는 그냥 오름차순으로 했다고 가정했기 때문에 1 - > 5 - > 2.... 순으로 가도 됨

# 큐를 이용한 방법 / 스택을 이용하기 위한 방법 사용 가능

 

from collections import deque

v,e = map(int,input().split())

#모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0]*(v+1)

#각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v+1)]

for _ in range(e):
    a,b = map(int,input().split())
    graph[a].append(b) #정점 A에서 B로 이동 가능

    #진입 차수를 1 증가 B의 들어오는 진입차수가 있다는 의
    indegree[b] += 1

def topology_sort():
    result = []
    q = deque() #큐 기능을 위한 deque 라이브러리 사용
    #처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    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
            #새롭게 진입차수가 0이 되는 노드를 큐에 삽
            if indegree[i]==0:
                q.append(i)
    for i in result:
        print(i,end=' ')
topology_sort()

입력 예시
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4