위상 정렬은 그래프에서 정점들을 순서에 맞게 정렬하는 알고리즘입니다. 해당 알고리즘은 방향 그래프에서만 적용이 가능하며, 사이클이 없는 경우에만 사용할 수 있습니다.

일반적으로 위상 정렬은 작업의 선후관계를 나타내는 그래프에서 각 작업을 수행하는 순서를 결정하기 위해 사용됩니다. 예를 들어, 프로젝트의 일련의 작업들을 수행할 때 어떤 작업들이 선행 작업이 되어야 하는지를 결정하는 데에 위상 정렬을 활용할 수 있습니다.

위상 정렬 알고리즘

위상 정렬 알고리즘은 일반적으로 DFS(Depth-First Search)를 기반으로 구현됩니다. 아래는 위상 정렬 알고리즘의 기본적인 구현 코드입니다.

def topological_sort(graph):
    # 그래프의 정점의 개수
    n = len(graph)
    
    # 방문 여부를 저장하는 배열
    visited = [False] * n
    
    # 정렬된 정점을 저장하는 배열
    result = []
    
    def dfs(node):
        visited[node] = True
        
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        
        result.append(node)
    
    # 모든 정점에 대해 DFS 수행
    for node in range(n):
        if not visited[node]:
            dfs(node)
    
    # 결과를 역순으로 반환하여 위상 정렬 결과를 얻음
    result.reverse()
    return result

위상 정렬의 응용

위상 정렬은 다양한 문제에서 응용될 수 있습니다. 몇 가지 예시를 살펴보겠습니다.

작업 스케줄링

프로젝트나 작업 관리 시스템에서 위상 정렬은 작업들의 선후관계를 나타내는 그래프에서 각 작업을 수행하는 순서를 결정하는 데에 사용됩니다. 작업들은 정점으로 표현되며, 작업들 간의 의존 관계는 간선으로 표현됩니다.

컴파일러

컴파일러는 소스 코드를 기계어로 변환하는 과정에서 위상 정렬을 사용합니다. 소스 코드는 그래프 형태로 표현되며, 각각의 정점은 컴파일되어야 할 코드 블록을 의미합니다. 간선은 코드 블록 간의 의존 관계를 나타내며, 위상 정렬을 통해 컴파일러는 코드 블록들의 올바른 컴파일 순서를 결정합니다.

의존성 관리

소프트웨어 개발 프로젝트에서 여러 모듈이 서로 의존하는 경우, 위상 정렬은 각 모듈의 의존성 관리에 사용될 수 있습니다. 모듈들은 정점으로 표현되며, 의존 관계는 간선으로 표현됩니다. 위상 정렬을 수행하면 모듈들을 올바른 순서로 빌드하거나 배포할 수 있습니다.

결론

위상 정렬은 방향 그래프에서 작업의 선후관계를 나타내는 그래프에서 각 작업을 수행하는 순서를 결정하는 데에 사용되는 알고리즘입니다. 위상 정렬의 기본 구현 방법을 이해하고 응용 사례를 살펴보았습니다. 이러한 알고리즘은 프로젝트 관리, 컴파일링, 의존성 관리 등 다양한 분야에서 유용하게 활용될 수 있습니다.