[알고리즘] 파이썬으로 위상정렬 구현하기 | Kahn Algorithm, 진입 차수, 순서를 부여하는 문제 해결

위상 정렬(Topology sort)은 방향 그래프에서 노드 순서를 찾을 수 있는 알고리즘입니다. 이 정렬은 대학의 선수과목 프레임워크와 같이 수강 순서가 주어지는 경우를 찾는데 활용할 수 있습니다. 작업 스케줄링, 프로세스 순서 결정, 의존성 해결 등 다양한 문제에서 활용할 수 있습니다.

 

위상 정렬 알고리즘은 크게 DFS와 Kahn의 알고리즘이 존재합니다. DFS는 이전에 공부했기에 여기서는 Kahn의 알고리즘을 살펴보려고 합다.

단계 1 : 진입 차수 계산

진입 차수(in-degree)는 해당 노드로 들어오는 에지 개수를 의미합니다. Kahn 알고리즘에서는 진입 차수를 기반으로 위상 정렬을 수행하기 때문에 진입 차수를 계산해야 합니다. 엣지에 대한 정보를 기반으로 진입 차수를 계산합니다. 

 

# 진입 차수 배열
in_degree = [0] * vertices

# 그래프 인접 리스트 초기화
graph = [[] for _ in range(vertices)]

# 간선 정보 추가 및 진입 차수 계산
for u, v in edges:
    graph[u].append(v)
    in_degree[v] += 1

단계 2 : 진입 차수 0인 노드 삽입

진입 차수가 0인 노드를 큐에 삽입합니다. 

 

# 진입 차수가 0인 노드를 큐에 삽입
queue = deque([i for i in range(vertices) if in_degree[i] == 0])

단계 3 : 위상 정렬 수행

정렬은 아래와 같은 순서로 큐가 빌 때까지 반복합니다.

• 큐에서 노드를 꺼내 정렬된 리스트에 추가
• 해당 노드와 연결된 모든 노드의 진입 차수 1 감소
• 만약 진입 차수가 0이 된 노드는 큐에 삽입

# 위상 정렬 결과를 저장할 리스트
topological_order = []

# 큐가 빌 때까지 반복
while queue:
    node = queue.popleft()
    topological_order.append(node)

    # 해당 노드와 연결된 모든 노드의 진입 차수를 감소시키고
    # 진입 차수가 0이 된 노드를 큐에 추가
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)

단계 4 : 정렬 확인 (사이클 여부 판별)

단계 3이 마무리되면(즉, 큐가 다 비었을 때) 정렬이 잘 되었는지 확인합니다. 확인하는 방법은 노드의 개수와 위상 정렬 결과의 개수가 일치하게 되면 위상 정렬이 정상적으로 수행되었다는 것을 의미합니다. (반대로, 다르다면 위상 정렬이 불가능한 그래프에 사이클이 존재하는 경우 입니다)

 

# 그래프에 사이클이 존재하면 위상 정렬 불가능
if len(topological_order) != vertices:
    print("Cycle")
    return []

전체 코드

위 단계에 따라 만들어진 전체 코드는 아래와 같습니다. 

from collections import deque

def topological_sort(vertices, edges):
    in_degree = [0] * vertices
    graph = [[] for _ in range(vertices)]
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque([i for i in range(vertices) if in_degree[i] == 0])
    
    topological_order = []
    while queue:
        node = queue.popleft()
        topological_order.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(topological_order) != vertices:
        return []
    
    return topological_order

참고자료

[1] https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬 - 위키백과, 우리 모두의 백과사전

[2] Do it! 알고리즘 코딩 테스트 : 파이썬 편