[python] 위상 정렬

07 Dec 2023

python

위상 정렬은 방향 그래프의 노드들을 임의의 순서로 나열하는 알고리즘입니다. 이 알고리즘은 어떤 일련의 작업을 수행하는 순서를 결정할 때 많이 사용됩니다.

알고리즘 개요

진입 차수가 0인 모든 노드를 큐에 넣습니다.
큐에서 노드를 하나씩 꺼내고 해당 노드와 연결된 간선을 삭제합니다.
간선 삭제 후 진입 차수가 0이 된 노드를 큐에 넣습니다.
큐가 빌 때까지 반복합니다.

예시 코드

from collections import deque

def topological_sort(graph):
    result = []
    indegree = [0] * len(graph)

    for nodes in graph.values():
        for node in nodes:
            indegree[node] += 1

    queue = deque()

    for i in range(len(indegree)):
        if indegree[i] == 0:
            queue.append(i)

    while queue:
        node = queue.popleft()
        result.append(node)

        for connected_node in graph[node]:
            indegree[connected_node] -= 1
            if indegree[connected_node] == 0:
                queue.append(connected_node)

    return result

예시 그래프

graph = {
    0: [],
    1: [2, 5],
    2: [3, 4],
    3: [],
    4: [],
    5: []
}

result = topological_sort(graph)
print(result)  # Output: [0, 1, 2, 5, 4, 3]

시간 복잡도

위상 정렬의 시간 복잡도는 O(V + E)입니다. V는 노드의 수, E는 간선의 수입니다.

마무리

위상 정렬은 작업의 선후 관계를 파악하여 순서를 결정할 때 유용한 알고리즘입니다. Python을 사용하여 위상 정렬을 쉽게 구현할 수 있습니다. 위상 정렬은 다양한 문제에서 응용될 수 있으므로, 알고리즘 개념을 익혀 활용해보세요.

참고 자료:

Topological sorting