로고

위상 정렬 이해하기: 그래프 알고리즘의 핵심

작성일 :

위상 정렬 이해하기: 그래프 알고리즘의 핵심

위상 정렬이란?

위상 정렬(Topological Sorting)은 방향성이 있는 비순환 그래프(Directed Acyclic Graph, DAG)의 노드를 순서대로 나열하는 작업을 의미합니다. 위상 정렬은 노드 A에서 노드 B로 가는 경로가 있는 경우, 나열된 순서에서 항상 A가 B의 앞에 오도록 합니다. 일상생활의 많은 문제들이 이러한 형식으로 표현될 수 있기 때문에, 위상 정렬은 다양한 응용 분야에서 중요합니다.

위상 정렬의 작동 원리

위상 정렬은 주로 두 가지 방법으로 구현됩니다: DFS(Depth-First Search) 기반 방법과 Kahn's Algorithm입니다. 이 두 방법은 위상 정렬을 구현하는 데 있어 각각의 특징과 장단점을 가지고 있습니다.

DFS 기반 방법

DFS 기반 방법은 재귀를 사용하여 그래프의 각 노드를 탐색합니다. 노드를 방문하고, 모든 인접한 노드를 방문한 후에 해당 노드를 스택에 저장합니다. 모든 노드를 탐색한 후, 스택을 역순으로 꺼내면 위상 정렬 결과가 됩니다. 아래는 기본적인 구현 코드입니다:

python
# Python3 DFS-based topological sort
from collections import defaultdict

# 그래프 클래스 정의
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def topologicalSortUtil(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.topologicalSortUtil(i, visited, stack)
        stack.insert(0, v)

    def topologicalSort(self):
        visited = [False] * self.V
        stack = []
        for i in range(self.V):
            if not visited[i]:
                self.topologicalSortUtil(i, visited, stack)
        print(stack)

# 예제 사용법
if __name__ == '__main__':
    g = Graph(6)
    g.addEdge(5, 2)
    g.addEdge(5, 0)
    g.addEdge(4, 0)
    g.addEdge(4, 1)
    g.addEdge(2, 3)
    g.addEdge(3, 1)

    print("Topological Sort of the given graph:")
    g.topologicalSort()

Kahn's Algorithm

Kahn's Algorithm은 BFS(Breadth-First Search)를 기반으로 한 방법입니다. 모든 노드의 진입 차수(In-degree)를 계산합니다. 진입 차수가 0인 노드를 큐에 넣고, 큐에서 노드를 제거하면서 인접한 노드의 진입 차수를 감소시킵니다. 다시 진입 차수가 0이 된 노드를 큐에 추가하는 과정을 반복합니다. 이를 통해 위상 정렬을 수행합니다.

python
# Python3 Kahn's Algorithm for topological sorting
from collections import deque, defaultdict

# 위상 정렬 알고리즘
def topologicalSort(vertices, edges):
    in_degree = {i: 0 for i in range(vertices)}
    graph = defaultdict(list)

    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])
    topo_order = []

    while queue:
        vertex = queue.popleft()
        topo_order.append(vertex)

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

    if len(topo_order) == vertices:
        return topo_order
    else:
        return []

# 예제 사용법
if __name__ == '__main__':
    vertices = 6
    edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
    print("Topological Sort of the given graph:", topologicalSort(vertices, edges))

위상 정렬의 실용 예제

  1. 프로젝트 일정 관리: 프로젝트 내 작업들이 의존성을 가지는 경우 위상 정렬을 사용해서 작업 순서를 결정할 수 있습니다.
  2. 컴파일러 최적화: 컴파일러가 코드 모듈을 컴파일하는 순서를 결정할 때, 모듈 간의 의존성을 고려하여 위상 정렬을 수행합니다.
  3. 수강 과목 선택 순서: 학생이 수강해야 하는 과목들이 선수 조건을 가지는 경우 위상 정렬을 통해 과목들의 수강 순서를 정합니다.
  4. 소프트웨어 빌드 시스템: 소프트웨어의 개별 구성 요소들이 빌드되기 위한 순서를 위상 정렬을 사용해서 결정합니다.

결론

위상 정렬은 다양한 분야에서 문제 해결을 위한 강력한 도구입니다. DFS와 Kahn's Algorithm 두 가지 방법을 통해 위상 정렬을 구현할 수 있으며, 이를 통해 복잡한 의존성 문제를 체계적으로 해결할 수 있습니다. 위상 정렬을 통해 그래프 이론의 기본 개념을 이해하고 실제 문제에 적용함으로써 문제 해결 능력을 향상시킬 수 있습니다.