[알고리즘 개념] 위상 정렬

0. 위상 정렬이란?

• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

진입차수

특정한 노드로 들어오는 간선의 개수

진출차수

특정한 노드에서 나가는 간선의 개수

1. 위상정렬의 동작과정

1. 진입차수가 0 인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2) 새롬게 진입차수가 0이 된 노드를 큐에 넣는다.

2. 위상정렬의 특징

• 위상 정렬은 DAG(순환하지 않는 방향 그래프)에 대해서만 수행 가능
• 여러가지 답이 존재할 수 있음
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재할 수 있다고 판단 가능
• 스택을 활용한 DFS를 이용해 위상 정렬을 수행 할 수 있음

3. 코드

from sys import stdin as s
from collections import deque
import sys
sys.setrecursionlimit(10**6)

s=open("input.txt","rt")

v,e = map(int,s.readline().split())
#진입 차수 테이블 초기화
indegree = [0]*(v+1)
#그래프 데이터 담을 인접 리스트 초기화
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a,b = map(int,s.readline().split())
    graph[a].append(b)
    # 진입 차수 추가 a->b이기 때문에 진입 차수 추가
    indegree[b]+=1

#위상 정렬 함수
def topology_sort():
    result=[] # 알고리즘 수행 결과를 담을 리스트
    q=deque() # 큐 기능을 위한 deque 라이브러리 사용
    for i in range(1,v+1):
        if indegree[i]==0:
            q.append(i)
            
    while q:
        node = q.popleft()
        result.append(node)
        for next in graph[node]:
            #해당 윈소와 연결된 노드들의 진입 차수에서 1 빼기
            indegree[next]-=1
            #새롭게 진입차수가 0이되는 노드를 큐에 삽입
            if indegree[next]==0:
                q.append(next)
    # 위상 정렬을 수행한 결과 출력
    for i in result:
        print(i,end=' ')
        
topology_sort()

Ref) 이것이 취업을 위한 코딩테스트다 with 파이썬
https://techblog-history-younghunjo1.tistory.com/264