위상 정렬(Topological Sort)

오늘은 위상정렬(Topological Sort)에 대해 알아보겠습니다!

 

위상정렬은 방향그래프, 사이클이 없는 그래프(DAG, Directed Acyclic Graph) 에서 노드의 순서를 정하는 알고리즘입니다!

(사이클이 있다면 시작점을 정할 수 없으므로 순서를 파악할 수 없음)

 

일반화 한다면, 순서가 정해져 있는 작업에서 조건에 맞게 순서를 결정해주는 것을 말합니다!

대표적인 예시로 선수과목 순서에 따라 수강과목을 정하기, 작업 스케줄링에 따라 작업순서 선정 등이 있습니다

특히 결과로 여러 답이 존재합니다! (유니크한 결과 X)

 

# 동작과정 

위상정렬은 2가지 방식으로 구현가능한데욥

1) 스택(stack)이용 - DFS

2) 큐(queue)이용 - BFS

일반적으로 큐를 이용한 방식이 주로 사용되므로 해당 방식을 선택하겠습니다

 

총 5가지의 단계로 구성되어 있습니다

 

1. 진입 차수(indegree) 계산

진입차수 리스트 생성 (각 노드로 들어오는 간선의 개수)

 

2. 진입 차수가 0인 노드를 큐에 삽입

3. 큐에서 노드를 하나씩 꺼내며 연결된 간선 제거
큐에서 노드를 꺼내고, 해당 노드와 연결된 모든 간선을 제거, 연결된 노드의 진입 차수를 1씩 줄임

 

4. 간선제거 이후 진입차수 0인 노드 큐에 삽입

새롭게 진입 차수가 0이 된 노드를 큐에 추가

 

5. 큐가 빌 때까지 3,4 과정 반복

특히 모든 원소 방문 전, 큐가 비어있게 되는 경우에는 사이클(cycle)이 존재하는 그래프가 되며

모든 원소에 방문 한 경우 큐에서 꺼낸 순서가 위상정렬 결과가 됩니다!

 

 

구체적인 예시를 통해 알아봅시다!

1,2,3,4,5 노드로 구성된 방향 그래프에서 위상정렬 순서를 알아보겠습니다!

 

 

결국 1,2,3,4,5의 순서가 반환됩니다!

 

# Python 코드

동작과정을 기반으로 큐를 이용하여 위상정렬을 구현해 보았습니다

구현시 인접 리스트 생성, 진입차수 리스트 생성, 기록할 큐 생성, while문을 이용한 위상정렬 수행과정 4가지 과정이 필요합니다

lst = [[] for _ in range(n+1)] # 인접 리스트

indegree = [0] * (n+1) # 진입차수 / 인덱스 -> 노드 / 값 -> 진입차수

# 진입차수 리스트 생성

for _ in range(m):

    a, b= map(int,sys.stdin.readline().split())

    lst[a].append(b)

    indegree[b] +=1 # 진입차수 증가

queue = deque()

for i in range(1,len(indegree)): # 진입차수 0인노드 큐에추가

    if indegree[i] == 0:

        queue.append(i)

while queue: # 위상정렬 수행

    idx = queue.popleft() # 큐에서 원소 꺼내기

    print(idx, end = ' ')

    for i in lst[idx]: # 연결된 간선 진입차수 1씩 뺌

        indegree[i] -=1

        if indegree[i] == 0: # 진입차수 0일시 다시 추가

            queue.append(i)

 

# 성능분석 - 시간복잡도

V-> 노드의 수

E-> 간선의 수

 

1) 진입 차수 계산

모든 간선을 한 번씩 확인해야하므로 O(E) 

 

2) 큐에서 노드를 하나씩 꺼내기

큐에서 노드를 꺼내고 연결된 간선 제거는 모든 노드와 간선에 대해 한번씩 수행됨 O(V + E) 

 

즉, O(E) + O(V + E) = O(V + E) 

 

# 관련문제

백준 2252번 - 줄 세우기

https://www.acmicpc.net/problem/2252

 

백준 1516번 - 게임 개발

https://www.acmicpc.net/problem/1516

 

백준 1948번 - 임계경로

https://www.acmicpc.net/problem/1948

 

 

# reference

파이썬 자료구조와 알고리즘: for beginner. (2021). 대한민국: 한빛아카데미.

Do it! 알고리즘 코딩 테스트 - 파이썬 편(김종관 저/이지스퍼블리싱 (주))