위상 정렬(Topological Sorting)의 정의와 특징

위상 정렬(Topological Sorting)의 정의와 특징

정의

위상 정렬은 유향 그래프에서 모든 노드를 "방향"을 고려하여 선형으로 정렬하는 알고리즘입니다. 즉, 그래프의 모든 간선(또는 아크) ( (u, v) )에서 ( u )가 ( v )보다 먼저 오도록 정렬합니다.

특징

1. 유향 그래프: 위상 정렬은 유향 그래프에서만 적용됩니다.
2. 비순환 그래프: 유향 순환 그래프에서는 위상 정렬이 불가능합니다.
3. 여러 가능한 답: 하나의 그래프에 여러 개의 유효한 위상 정렬이 존재할 수 있습니다.
4. 큐 또는 스택 사용: 보통 입력 차수(Indegree)를 관리하는 큐나 스택을 사용하여 구현됩니다.

사용 예

1. 작업 스케줄링: 여러 작업과 그 사이의 의존 관계를 표현하고 실행 순서를 결정할 때
2. 컴파일러: 여러 모듈이나 함수의 의존성을 고려하여 컴파일 순서를 결정할 때
3. 과목 선택: 선수 과목을 고려하여 수업을 들을 순서를 결정할 때

C와 Python에서의 비교

C

C에서 위상 정렬을 구현할 때는 보통 배열과 연결 리스트를 사용하여 그래프를 표현하고, 큐를 사용하여 입차수를 관리합니다. 메모리 할당과 해제를 명시적으로 해야 합니다.

#include <stdio.h>
#include <stdlib.h>
// ... (그래프와 큐의 구현)

void topologicalSort(Graph* graph) {
    // ... (입력 차수와 큐를 사용한 위상 정렬 구현)
}

Python

Python에서는 list나 deque 자료형을 사용하여 상대적으로 간단하게 위상 정렬을 구현할 수 있습니다. Python의 동적 타이핑과 라이브러리가 작업을 더욱 간편하게 만듭니다.

from collections import deque

def topological_sort(graph):
    indegree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] += 1

    queue = deque([node for node in graph if indegree[node] == 0])
    sorted_nodes = []

    while queue:
        current = queue.popleft()
        sorted_nodes.append(current)

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

    return sorted_nodes

graph = {'A': ['D', 'F'], 'B': ['D', 'E'], 'C': ['F'], 'D': ['G'], 'E': ['G'], 'F': [], 'G': []}
print(topological_sort(graph))

정리

C는 성능과 메모리 관리 측면에서 더 많은 컨트롤을 가능하게 하지만, 구현이 복잡할 수 있습니다. 반면 Python은 표준 라이브러리와 간결한 문법을 활용하여 빠르고 쉽게 구현할 수 있습니다.