6-7. 그래프: 위상 정렬

1. 위상 정렬의 기본 개념

위상 정렬(Topological Sorting)은 방향 비순환 그래프(Directed Acyclic Graph, DAG)의 노드들을 선형 순서로 정렬하는 알고리즘입니다. 여기서 선형 순서란, 그래프의 모든 간선 (u, v)에 대해 노드 u가 노드 v보다 반드시 먼저 정렬되는 순서를 의미합니다. 즉, 작업의 의존성을 고려하여 작업을 수행해야 하는 순서를 결정하는 데 사용됩니다.

1) DAG (Directed Acyclic Graph)

위상 정렬은 DAG에서만 적용 가능합니다. DAG는 사이클이 없는 방향 그래프를 의미합니다. 사이클이 존재하면, 노드 간의 순환 의존성이 발생하여 위상 정렬이 불가능해집니다.

2) 예시: 작업 스케줄링

위상 정렬은 다양한 분야에서 활용됩니다. 예를 들어, 프로젝트의 작업 스케줄링을 생각해 봅시다. 각 작업은 노드로, 작업 간의 선행 관계는 간선으로 표현될 수 있습니다. 위상 정렬을 통해 작업을 수행해야 하는 순서를 결정할 수 있습니다.

위 그림은 작업 스케줄링의 예시를 보여줍니다. 각 작업 (A, B, C, D, E, F)은 노드로 표현되고, 작업 간의 의존 관계는 간선으로 표시됩니다. 예를 들어, 작업 C는 작업 A와 B가 완료된 후에 시작할 수 있습니다. 위상 정렬을 적용하면, A -> B -> C -> D -> E -> F 와 같은 유효한 작업 순서를 얻을 수 있습니다.

2. 위상 정렬 알고리즘: Kahn's Algorithm

가장 널리 사용되는 위상 정렬 알고리즘 중 하나는 Kahn의 알고리즘입니다. Kahn의 알고리즘은 진입 차수(indegree)를 기반으로 합니다. 진입 차수는 특정 노드로 들어오는 간선의 개수를 의미합니다.

1) 알고리즘 단계

Kahn의 알고리즘은 다음과 같은 단계를 거칩니다.

1. 진입 차수 계산: 모든 노드의 진입 차수를 계산합니다.
2. 시작 노드 선택: 진입 차수가 0인 모든 노드를 큐에 추가합니다. (시작 노드는 다른 노드에 의존하지 않는 노드입니다.)
3. 반복: 큐가 비어있지 않은 동안 다음을 반복합니다.
   • 큐에서 노드 u를 꺼내 정렬된 결과에 추가합니다.
   • 노드 u에서 나가는 모든 간선 (u, v)에 대해, 노드 v의 진입 차수를 1 감소시킵니다.
   • 노드 v의 진입 차수가 0이 되면, 노드 v를 큐에 추가합니다.
4. 사이클 검사: 정렬된 결과에 모든 노드가 포함되지 않으면, 그래프에 사이클이 존재하는 것입니다.

2) 알고리즘 구현 (Python)

from collections import deque

def topological_sort(graph):
    """
    Kahn's Algorithm을 이용한 위상 정렬 구현
    :param graph: 인접 리스트로 표현된 그래프 (딕셔너리)
    :return: 위상 정렬된 노드 리스트, 사이클 존재 시 None 반환
    """
    in_degree = {}
    for node in graph:
        in_degree[node] = 0

    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1

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

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

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

    if len(sorted_nodes) != len(graph):
        return None  # 사이클 존재
    else:
        return sorted_nodes

3) 예시 적용

위 코드에서 graph는 인접 리스트로 표현된 그래프입니다. 예를 들어, 아래와 같은 그래프가 주어졌다고 가정해 봅시다.

graph = {
    'A': ['C', 'B'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E', 'F'],
    'E': [],
    'F': []
}

이 그래프에 topological_sort 함수를 적용하면, 다음과 같은 위상 정렬 결과를 얻을 수 있습니다 (결과는 여러 가지가 가능하며, 이 중 하나를 반환합니다).

['A', 'B', 'C', 'D', 'E', 'F']

3. 위상 정렬 알고리즘: DFS 기반

위상 정렬은 DFS(Depth-First Search, 깊이 우선 탐색)를 이용해서도 구현할 수 있습니다. DFS 기반 위상 정렬은 그래프의 각 노드를 방문하면서, 후위 순회(postorder) 방식을 활용합니다. 후위 순회는 자식 노드를 먼저 방문한 후, 부모 노드를 방문하는 방식입니다.

1) 알고리즘 단계

DFS 기반 위상 정렬은 다음과 같은 단계를 거칩니다.

1. 방문 여부 표시: 모든 노드의 방문 여부를 False로 초기화합니다.
2. DFS 수행: 그래프의 각 노드에 대해 DFS를 수행합니다.
   • 현재 노드를 방문 처리합니다.
   • 현재 노드의 인접 노드에 대해, 아직 방문하지 않았다면 DFS를 재귀적으로 호출합니다.
   • 현재 노드의 모든 인접 노드 방문이 끝나면, 현재 노드를 결과 리스트의 맨 앞에 추가합니다. (후위 순회 방식)
3. 사이클 검사: DFS 수행 중, 이미 방문한 노드를 다시 방문하는 경우, 그래프에 사이클이 존재합니다.

2) 알고리즘 구현 (Python)

def topological_sort_dfs(graph):
    """
    DFS를 이용한 위상 정렬 구현
    :param graph: 인접 리스트로 표현된 그래프 (딕셔너리)
    :return: 위상 정렬된 노드 리스트, 사이클 존재 시 None 반환
    """
    visited = {}
    for node in graph:
        visited[node] = False
    sorted_nodes = []

    def dfs(node):
        visited[node] = True
        for neighbor in graph.get(node, []):
            if not visited[neighbor]:
                if not dfs(neighbor):  # 사이클 감지
                    return False
            elif neighbor in sorted_nodes:  # 이미 정렬된 노드를 재방문하면 사이클
                return False
        sorted_nodes.insert(0, node)  # 후위 순회
        return True

    for node in graph:
        if not visited[node]:
            if not dfs(node):  # 사이클 감지
                return None
    return sorted_nodes

3) 예시 적용

이전과 동일한 graph를 사용하여 topological_sort_dfs 함수를 실행하면, 다음과 같은 위상 정렬 결과를 얻을 수 있습니다.

['A', 'C', 'B', 'D', 'E', 'F']

4. 위상 정렬의 응용 및 활용

위상 정렬은 다양한 실무 문제에 적용될 수 있습니다.

1) 작업 스케줄링

가장 일반적인 응용 분야입니다. 작업 간의 의존성을 파악하고, 작업을 수행해야 하는 순서를 결정합니다.

2) 선수과목

수강해야 할 선수과목이 있는 경우, 수강해야 할 과목의 순서를 결정하는 데 사용할 수 있습니다.

3) 컴파일러

컴파일러는 소스 코드의 의존성을 분석하여 모듈의 컴파일 순서를 결정하는 데 위상 정렬을 사용할 수 있습니다.

4) 데이터베이스

데이터베이스의 테이블 간 참조 관계를 파악하고, 테이블의 생성 순서를 결정하는 데 활용됩니다.

5) dependency resolver

소프트웨어 패키지 관리 시스템에서 패키지 간의 의존성을 해결하고, 패키지의 설치 순서를 결정하는 데 사용됩니다.

5. 주의사항 및 트러블슈팅

1) 사이클 감지

위상 정렬 알고리즘에서 가장 중요한 부분은 사이클 감지입니다. 사이클이 존재하면 위상 정렬은 불가능합니다. Kahn의 알고리즘에서는 큐에 추가할 노드가 없는 경우 (큐가 비어있지만, 아직 처리되지 않은 노드가 있는 경우) 사이클이 존재한다고 판단합니다. DFS 기반 알고리즘에서는 DFS 탐색 중에 이미 방문한 노드를 다시 방문하는 경우 사이클을 감지합니다.

2) 여러 가지 유효한 정렬 순서

위상 정렬 결과는 유일하지 않을 수 있습니다. 즉, 여러 가지 유효한 정렬 순서가 존재할 수 있습니다. 예를 들어, 두 노드 사이에 의존 관계가 없는 경우, 두 노드의 순서는 자유롭게 바뀔 수 있습니다.

3) 효율성

Kahn의 알고리즘과 DFS 기반 위상 정렬 모두 시간 복잡도 O(V + E)를 가집니다. 여기서 V는 노드의 개수, E는 간선의 개수입니다. 이는 위상 정렬 알고리즘이 그래프의 크기에 선형적으로 비례하는 효율적인 알고리즘임을 의미합니다.

4) 구현 시 고려 사항

• 그래프 표현 방식: 인접 리스트를 사용하는 것이 일반적이며, 각 노드의 인접 노드를 효율적으로 접근할 수 있습니다.
• 데이터 구조: Kahn의 알고리즘에서는 큐를 사용하여 진입 차수가 0인 노드를 관리합니다. DFS 기반 알고리즘에서는 스택 (재귀 호출)을 활용합니다.
• 예외 처리: 그래프가 DAG가 아닌 경우 (사이클 존재), 적절한 오류 처리 (예: None 반환)를 수행해야 합니다.

6. 결론

위상 정렬은 작업 순서 결정, 선수 과목 설정, 컴파일 순서 지정 등 다양한 분야에서 활용되는 핵심적인 알고리즘입니다. Kahn의 알고리즘과 DFS 기반 알고리즘을 이해하고, 실무에서 문제 해결에 적용할 수 있도록 숙달하는 것이 중요합니다.