[자료구조] 위상 정렬

채멈·2024년 3월 17일

python 자료구조

자료구조

목록 보기

4/4

위상 정렬(Topology Sort)

위상 정렬 : 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘
ex) 대학 선수 과목

위상 정렬의 특징

여러 개의 답이 존재할 수 있음
DAG(Directed Acycle Graph)에만 적용 가능 - 사이클이 발생하지 않는 방향 그래프
즉, 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음

사이클이 존재하는 경우는 왜 안될까?

위상 정렬은 시작점이 존재 해야 하는 데, 사이클 그래프에서는 시작점부터 찾을 수가 없다. 따라서 순서를 정할 수 없기 때문에 사이클이 존재하는 경우는 위상 정렬을 수행할 수 없음

Queue를 사용한 위상 정렬 알고리즘

진입차수가 0인 정점을 큐에 삽입
큐에서 원소를 꺼내 연결된 모든 간선을 제거
간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입
큐가 빌 때까지 2~3번 과정을 반복. 모든 원소를 방문하기 전에 큐가 빈 다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의

-> 즉, 항상 진입차수가 0인 정점을 큐에 넣는 과정 만으로 위상 정렬을 수행할 수 있음

위상 정렬 코드

from collections import deque
 
v, e = map(int, input().split())
 
indegree = [0] * (v + 1)
graph = [[] for _ in range(v + 1)]
 
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
 
 
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()

위상정렬의 시간 복잡도

O(V + E) : 정점의 개수 + 간선의 개수