[알고리즘 이론] 위상 정렬(Topological Sorting)

위상 정렬(Topological Sort) 알고리즘 이해하기

위상 정렬은 방향 그래프(Directed Graph)에서 정점들을 선형으로 나열하는 알고리즘입니다. 이 알고리즘은 선행 관계가 있는 작업들을 순서대로 나열할 때 매우 유용합니다. 오늘은 위상 정렬의 개념부터 구현 방법까지 자세히 알아보겠습니다.

위상 정렬이란?

위상 정렬은 방향 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 "선행 순서를 지키는 순서"로 나열하는 알고리즘입니다. 여기서 중요한 것은 그래프에 사이클이 없어야 한다는 점입니다. 사이클이 있다면 선후 관계가 모순되어 위상 정렬을 수행할 수 없습니다.

예를 들어, 대학 수업의 선수과목 관계를 생각해봅시다:

• 자료구조를 듣기 위해서는 프로그래밍 기초를 들어야 함
• 알고리즘을 듣기 위해서는 자료구조를 들어야 함
• 운영체제를 듣기 위해서는 알고리즘을 들어야 함

이러한 관계를 그래프로 표현한 후 위상 정렬을 하면 "프로그래밍 기초 → 자료구조 → 알고리즘 → 운영체제"와 같은 순서를 얻을 수 있습니다.

위상 정렬의 활용 분야

위상 정렬은 다양한 분야에서 활용됩니다:

• 작업 스케줄링(프로젝트 관리)
• 대학 수업의 선수과목 계획
• 소프트웨어 패키지 의존성 관리
• 논리적 추론 시스템
• 컴파일러의 심볼 테이블 생성

위상 정렬 알고리즘

위상 정렬을 구현하는 대표적인 방법은 두 가지가 있습니다:

1. DFS(깊이 우선 탐색) 기반 알고리즘

DFS를 이용한 위상 정렬은 다음과 같이 진행됩니다:

1. 모든 정점에 대해 DFS를 수행합니다.
2. DFS가 끝나는 순서의 역순으로 정점을 나열합니다.

2. 진입 차수(Indegree) 기반 알고리즘

진입 차수는 해당 정점으로 들어오는 간선의 수를 의미합니다. 이를 이용한 위상 정렬은:

1. 진입 차수가 0인 정점을 큐에 넣습니다.
2. 큐에서 정점을 꺼내어 결과 리스트에 추가합니다.
3. 해당 정점에서 나가는 간선을 제거하고, 연결된 정점의 진입 차수를 1 감소시킵니다.
4. 진입 차수가 0이 된 정점을 큐에 넣습니다.
5. 큐가 빌 때까지 2~4를 반복합니다.

구현 예제

DFS를 이용한 위상 정렬과 진입 차수를 이용한 위상 정렬을 각각 구현해보겠습니다.

DFS를 이용한 위상 정렬 (Java)

 

java

import java.util.*;

public class TopologicalSortDFS {
    private int V;  // 정점의 수
    private ArrayList<ArrayList<Integer>> graph;  // 인접 리스트
    private Stack<Integer> stack;  // 결과를 저장할 스택
    private boolean[] visited;  // 방문 여부 체크
    
    public TopologicalSortDFS(int v) {
        V = v;
        graph = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            graph.add(new ArrayList<>());
        }
        stack = new Stack<>();
        visited = new boolean[v];
    }
    
    // 간선 추가
    public void addEdge(int u, int v) {
        graph.get(u).add(v);
    }
    
    // DFS 기반 위상 정렬
    public void topologicalSort() {
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        
        // 스택에서 역순으로 출력
        System.out.println("위상 정렬 결과:");
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
    
    private void dfs(int v) {
        visited[v] = true;
        
        // 인접 정점 방문
        for (Integer neighbor : graph.get(v)) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
        
        // 현재 정점을 스택에 추가
        stack.push(v);
    }
    
    public static void main(String[] args) {
        TopologicalSortDFS g = new TopologicalSortDFS(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);
        
        g.topologicalSort();
    }
}

진입 차수를 이용한 위상 정렬 (Python)

 

python

from collections import defaultdict, deque

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)  # 인접 리스트
        self.V = vertices  # 정점의 수
        
    def add_edge(self, u, v):
        self.graph[u].append(v)
        
    def topological_sort(self):
        # 진입 차수 계산
        in_degree = [0] * self.V
        for i in self.graph:
            for j in self.graph[i]:
                in_degree[j] += 1
                
        # 진입 차수가 0인 정점을 큐에 넣음
        queue = deque()
        for i in range(self.V):
            if in_degree[i] == 0:
                queue.append(i)
                
        # 위상 정렬 결과를 저장할 리스트
        result = []
        
        # 큐가 빌 때까지 반복
        while queue:
            # 큐에서 노드를 꺼내어 결과에 추가
            u = queue.popleft()
            result.append(u)
            
            # 인접 정점들의 진입 차수를 1 감소
            for i in self.graph[u]:
                in_degree[i] -= 1
                # 진입 차수가 0이 되면 큐에 추가
                if in_degree[i] == 0:
                    queue.append(i)
                    
        # 모든 정점이 결과에 포함되었는지 확인 (사이클 체크)
        if len(result) != self.V:
            print("그래프에 사이클이 존재합니다.")
            return None
        else:
            return result

# 테스트
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

result = g.topological_sort()
if result:
    print("위상 정렬 결과:", result)

시간 복잡도

두 알고리즘 모두 시간 복잡도는 O(V+E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다.

• DFS 방식: 각 정점은 한 번씩 방문하고, 각 간선도 한 번씩 확인합니다.
• 진입 차수 방식: 각 정점은 한 번씩 큐에 들어가고, 각 간선도 한 번씩 제거됩니다.

위상 정렬의 특징

1. 위상 정렬의 결과는 유일하지 않을 수 있습니다. 동일한 그래프에 대해 여러 가지 위상 정렬이 가능합니다.
2. 사이클이 존재하는 그래프에서는 위상 정렬을 수행할 수 없습니다.
3. 모든 DAG(Directed Acyclic Graph)는 적어도 하나의 위상 정렬이 가능합니다.

결론

위상 정렬은 선후 관계가 있는 작업들을 순서대로 나열하는 데 매우 유용한 알고리즘입니다. 특히 프로젝트 관리, 작업 스케줄링, 의존성 관리 등 다양한 분야에서 활용됩니다. 사이클이 없는 방향 그래프에서만 적용 가능하다는 제약이 있지만, 이를 고려하면 매우 효율적인 알고리즘입니다. DFS와 진입 차수 기반의 두 가지 구현 방법이 있으며, 문제 상황에 맞게 선택하여 사용할 수 있습니다.