[Python] 위상정렬 (Kahn 알고리즘, DFS 활용)

정의

위상정렬은 무순환 방향 그래프 DAG(Directed Acyclie Graph)에서 정돈되지 않은 그래프를, 각 노드의 선후관계를 정립해 일관된 방향으로 향하도록 정렬하는 방식이다. (작업의 우선순위, 부품의 조립 순서)

Kahn 알고리즘(BFS 기반)

각 노드의 진입차수(indegree) 계산 후, 진입 차수가 0인 노드를 큐에 넣고, 연결된 노드의 진입 차수를 감소

최종적으로 현재 진입 차수가 0인 노드를 선택

from collections import deque

def topological_sort_kahn(graph, indegree):
    result = []              # 위상 정렬 결과 저장
    queue = deque([i for i in range(1, len(indegree)) if indegree[i] == 0])

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(graph) - 1:  # 그래프에 사이클이 있는 경우
        return None
    return result

# 사용 예제:
n = 6
graph = {1: [2, 3],
         2: [4],
         3: [4, 5],
         4: [6],
         5: [6],
         6: []}
indegree = [0] * (n+1)
for u in graph:
    for v in graph[u]:
        indegree[v] += 1

print(topological_sort_kahn(graph, indegree))

DFS 위상정렬

DFS(깊이 우선 탐색)를 통해 각 노드에 대해 탐색을 진행하고,
재귀 호출이 끝난 후(백트래킹 시점)에 노드를 결과 리스트에 추가.
최종적으로 리스트를 역순으로 뒤집으면 위상 정렬 결과가 됨

def topological_sort_dfs(graph):
    visited = [False] * (len(graph) + 1)
    result = []

    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        result.append(node)

    for node in range(1, len(graph)):
        if not visited[node]:
            dfs(node)

    result.reverse()  # 역순으로 뒤집어 위상 정렬 결과 얻기
    return result

# 사용 예제:
graph = {1: [2, 3],
         2: [4],
         3: [4, 5],
         4: [6],
         5: [6],
         6: []}
print(topological_sort_dfs(graph))