배열을 활용한 위상 정렬 구현하기

06 Nov 2023

javascript

위상 정렬은 방향 그래프의 정점을 순서대로 나열하는 알고리즘입니다. 이를 통해 일련의 작업이나 이벤트의 선행 관계를 결정할 때 유용하게 사용될 수 있습니다.

알고리즘 개요

위상 정렬을 구현하기 위해 아래와 같은 단계를 거칩니다:

각 정점의 진입 차수를 계산합니다. (진입 차수란 해당 정점으로 들어오는 간선의 개수를 의미합니다)
진입 차수가 0인 정점을 큐에 추가합니다.
큐에서 정점을 하나씩 꺼내면서 해당 정점과 연결된 간선을 제거하고, 연결된 정점들의 진입 차수를 감소시킵니다.
진입 차수가 0이 된 정점을 큐에 추가합니다.
큐가 빌 때까지 3, 4 단계를 반복합니다.

구현 예시

아래는 배열을 활용하여 위상 정렬을 구현한 예시 코드입니다. 이 예시에서는 정점과 간선을 나타내기 위해 인접 행렬을 사용합니다. (정점 번호는 0부터 시작)

from collections import deque

def topological_sort(adj_matrix):
    num_vertices = len(adj_matrix)
    in_degrees = [0] * num_vertices
    result = []
    queue = deque()

    # 진입 차수 계산
    for v in range(num_vertices):
        for u in range(num_vertices):
            if adj_matrix[u][v] == 1:
                in_degrees[v] += 1

    # 진입 차수가 0인 정점 큐에 추가
    for v in range(num_vertices):
        if in_degrees[v] == 0:
            queue.append(v)

    # 큐가 빌 때까지 반복
    while queue:
        v = queue.popleft()
        result.append(v)

        # 연결된 간선 제거 및 진입 차수 감소
        for u in range(num_vertices):
            if adj_matrix[v][u] == 1:
                in_degrees[u] -= 1
                if in_degrees[u] == 0:
                    queue.append(u)

    # 결과 출력
    print("위상 정렬 결과:", result)

# 인접 행렬 예시
adj_matrix = [
    [0, 1, 1, 0],
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]

# 위상 정렬 호출
topological_sort(adj_matrix)

위의 예시 코드는 인접 행렬을 사용하여 위상 정렬을 구현하였습니다. 해당 코드는 Python으로 작성되었지만, 다른 프로그래밍 언어에서도 비슷한 방식으로 구현할 수 있습니다.

결론

위상 정렬은 방향 그래프의 정점들을 선후 관계에 따라 나열하는 알고리즘입니다. 배열을 활용하여 진입 차수를 계산하고, 큐를 사용하여 진입 차수가 0인 정점을 차례로 추출하는 방식으로 위상 정렬을 구현할 수 있습니다.

알고리즘 개요

구현 예시

결론

참고 자료