위상 정렬

위상 정렬(Topological Sort)은 방향성 그래프에서 각 정점을 선후 관계에 맞게 정렬하는 알고리즘이다. 이 알고리즘은 주로 작업이나 이벤트의 순서를 결정할 때 사용된다. 예를 들어, 여러 작업을 수행할 때 어떤 작업이 다른 작업보다 먼저 실행되어야 한다면, 이를 그래프 형태로 표현하고 위상 정렬을 통해 적절한 실행 순서를 도출할 수 있다.

위상 정렬은 사이클이 없는(비순환) 방향 그래프(Directed Acyclic Graph, DAG)에서만 적용된다. 순환이 존재하면, 어떤 작업을 먼저 해야 하는지 정할 수 없기 때문에 위상 정렬이 불가능하다.

위상 정렬 알고리즘의 주요 과정은 다음과 같다:

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

위상 정렬은 DFS(깊이 우선 탐색)나 BFS(너비 우선 탐색) 방식으로 구현할 수 있으며, 일반적으로 큐를 이용한 BFS 방식이 많이 사용된다. 시간 복잡도는 O(V + E)로, V는 정점의 수, E는 간선의 수이다.

위상 정렬 예시 코드

from collections import deque

n, m = map(int, input().split())
indegree = [0] * (n + 1)
graph = [[] for i in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def topological_sort():
    result = []
    q = deque()

    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        v = q.popleft()
        result.append(v)

        for i in graph[v]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=' ')

topological_sort()

위상 정렬

SERIES: 알고리즘 (9)

위상 정렬

위상 정렬 예시 코드

추천 문제