[TIL] 위상 정렬 Topology Sort

위상 정렬 Topology Sort

순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 
사이클이 없는 DAG 에만 적용이 가능하다 

 

DAG Directed Acyclic Graph

방향이 있는, 비순환적인 그래프

대학교의 선후수 과목에 비유할 수 있다

전자회로 과목은 회로이론과 기초전자회로실험 과목을 이수해야 수강이 가능하다 

여기에서 회로이론과 기초전자회로실험의 수강 순서는 중요하지 않다 

 

진입 차수와 진출 차수

위상 정렬 동작 과정을 보기 전에 진입 차수와 진출 차수에 대한 개념을 먼저 알아 두어야 한다 

진입 차수 Indegree 는 노드로 들어오는 간선의 개수이고

진출 차수 Outdegree 는 노드에서 나가는 간선의 개수이다 

위상 정렬 동작 과정

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

 각 노드가 큐에 들어온 순서가, 위상 정렬을 수행한 결과이다 

 

위상 정렬의 특징

1. 위상 정렬은 DAG (Directed Acyclic Graph) 에 대해서만 수행할 수 있다 

2. 위상 정렬에는 여러 가지 답이 존재할 수 있다 

3. 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다

4. 보통 큐를 사용하여 구현하지만, 스택과 DFS 를 이용한 방식으로도 구현할 수 있다 

 

위상 정렬 코드 구현

from collections import deque

# 위상 정렬 함수
def topological_sort(n, graph):
    # 모든 노드의 진입 차수 초기화
    in_degree = [0] * n
    for u in range(n):
        for v in graph[u]:
            in_degree[v] += 1

    # 진입 차수가 0인 노드들을 큐에 삽입
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    
    # 위상 정렬 결과 리스트
    topo_order = []

    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 노드를 하나 꺼내서 결과에 추가
        node = queue.popleft()
        topo_order.append(node)

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

    # 모든 노드를 방문하지 못하면 사이클이 존재하는 것
    if len(topo_order) != n:
        return None  # 사이클이 존재하는 경우

    return topo_order  # 위상 정렬 결과 반환

# 테스트용 그래프 (노드 0부터 시작)
n = 6  # 노드 수
graph = {
    0: [2, 3],  # 0번 노드에서 2, 3번 노드로
    1: [3, 4],  # 1번 노드에서 3, 4번 노드로
    2: [3],     # 2번 노드에서 3번 노드로
    3: [5],     # 3번 노드에서 5번 노드로
    4: [5],     # 4번 노드에서 5번 노드로
    5: []       # 5번 노드는 끝점
}

# # 사용자로부터 그래프 입력 받기
# def input_graph():
#     n = int(input("노드의 개수를 입력하세요: "))
#     graph = {}

#     for i in range(n):
#         edges = input(f"{i}번 노드에서 연결된 노드를 공백으로 구분하여 입력하세요 (없으면 그냥 엔터): ").strip()
#         if edges:
#             graph[i] = list(map(int, edges.split()))
#         else:
#             graph[i] = []
    
#     return n, graph

# n, graph = input_graph()

result = topological_sort(n, graph)
if result:
    print("위상 정렬 결과:", result)
else:
    print("사이클이 존재합니다.")

 

 

자료 구조

스택 DFS, 큐 - 칸스 정렬 (유명하고 많이 쓴다)

인접 리스트