신장 트리 (Spanning Tree)

신장 트리란 연결 그래프에서 모든 정점(n개)을 포함하면서

정점 수보다 하나 적은 개수(n-1개)의 간선만으로 이루어진 부분 그래프를 말한다.

spanning-tree

이러한 간선들의 모음은 그래프의 모든 정점을 연결하되 사이클(순환)이 없는 트리 구조를 이룬다.

이 때 하나의 그래프에는 여러 개의 신장 트리가 존재할 수 있다.

🤨 부분 그래프인건 알겠는데 왜 트리?

신장 트리는 말했듯이 모든 정점을 포함하는 간선 집합이다.

그렇기 때문에 임의의 한 정점을 루트로 삼더라도,

다른 모든 정점들과 계층 구조(부모-자식 관계)를 이루는 트리를 구성 가능한 트리성이 존재한다.

spanning-tree2

최소 신장 트리 (Minimum Spanning Tree, MST)

최소 신장 트리는 가중치 그래프의 여러 신장 트리 중 간선 가중치 합이 최소인 신장 트리를 의미한다.

minimum-spanning-tree => 가중치 합이 14인 최소 신장 트리

이 때 루트 선택에 따라 트리 모양은 달라지지만, 이는 루트 기준으로 트리를 몇 번 회전시켰을 뿐, 동일한 MST 구조이다.

minimum-spanning-tree2

무가중치 그래프의 경우 모든 간선의 가중치를 1로 간주하므로, 모든 신장 트리의 간선 가중치 합계는 항상 V-1로 동일하며 모두 최소 신장 트리에 해당한다.

MST의 중요성 및 실제 응용 사례

MST는 주어진 점들을 최소 비용으로 연결하는 최적화 수단으로서, 그래프 이론과 네트워크 설계 분야에서 중요한 역할을 한다.

현실 세계의 다양한 시스템을 그래프로 모델링하면 MST 개념을 통해 비용을 최소화한 연결 방식을 찾을 수 있다.

통신망 및 전산망 설계

도시들을 연결하는 통신 케이블이나 컴퓨터 네트워크의 배선 설계 시, 모든 지점을 연결하면서 총 연결 비용을 최소화하는 네트워크 구성을 MST로 찾을 수 있다.
전력망 및 배관망 구축

전력 공급망, 수도관, 가스관 등 인프라를 설계할 때 MST를 이용하면 각 시설을 모두 연결하면서도 배선이나 배관 길이(비용)를 최소화할 수 있다.

⇒ 실제로 최초의 MST 알고리즘은 효율적인 전력망 설계를 목적으로 1926년 체코의 과학자 보루브카에 의해 개발되었다.
회로 설계

인쇄회로기판에서 모든 회로 요소에 전원을 공급하는 배선망을 최소화할 수 있다.

이처럼 MST는 “모든 점들을 잇되 비용 합이 최소”라는 문제와 직접적으로 연관되므로, 다양한 분야에서 실제로 MST를 구함으로써 자원 절약과 효율성 증대를 이끌어낸다.

MST를 구하는 대표 알고리즘

MST를 구하는 알고리즘으로는 전통적으로 Prim 알고리즘과 Kruskal 알고리즘 두 가지가 많이 사용된다.

두 알고리즘 모두 탐욕(greedy) 기법을 사용하여 지역적으로 최선인 선택을 반복함으로써 전체 최적해 (MST)를 구하게 된다.

하지만 접근 방식과 자료구조 사용 면에서 차이가 있으므로 각각의 개념과 구현 원리 등을 상세히 알아보고 비교해보도록 하자.

Prim 알고리즘

prim

Prim 알고리즘은 임의의 정점에서 시작해 하나의 트리를 점진적으로 확장해 나가는 방식으로 MST를 구축하는 알고리즘이다.

Prim 알고리즘 단계별 전략

초기에는 MST에 단 하나의 정점만 포함된 상태에서 시작

⇒ 우선 하나의 정점을 취해 시작하면, 그 자체로 한 정점짜리 MST라 볼 수 있음. (v1단독으로 MST 시작)
현재까지 구성된 트리에 인접한 간선들 중 가장 가중치가 작은 간선을 선택하여 새로운 정점을 트리에 추가

⇒ 현재 MST에 가장 가까운(간선 가중치가 최소인) 인접 정점 v2와 그 간선 e1을 추가하면, 두 정점에 대한 MST가 된다.
이러한 과정을 모든 정점이 포함될 때까지(즉, n-1개의 간선이 선택될 때까지) 수행하다보면 결과적으로 최소 신장 트리가 완성된다.

프림 알고리즘을 위해서는 다음의 3가지 정보가 유지되어야 한다.

방문 여부(visited)

해당 정점이 MST에 포함되었는지 표시하는 불리언 값
MST와의 거리(distance)

현재까지 구성된 MST 부분집합에 이 정점을 가장 낮은 가중치로 연결시켜 줄 수 있는 간선의 가중치 (MST 부분트리와 정점 간의 최소 연결 비용)
부모 정점(parent)

해당 정점이 MST에 추가될 때 연결된 부모 정점 (즉, MST 내에서 이 정점을 연결해준 다 른 정점)

위 3가지 정보를 이용하여 Prim 알고리즘은 단계적으로 MST를 성장시킨다.

어떻게 가장 가중치가 작은 간선을 효율적으로 찾을까?

자, 이제 실제 구현을 생각해보자.

Prim 알고리즘의 핵심은 "현재까지 구성된 트리에 인접한 간선들 중 가장 가중치가 작은 간선을 선택" 하는 과정이다.

가장 단순한 방법은 매 단계마다 현재 MST에 연결된 모든 간선을 일일이 확인하며 최솟값을 찾는 것이다.

하지만 정점과 간선이 수천, 수만 개가 되면 이 과정은 매우 비효율적이게된다. 🐢

바로 이 "수많은 후보 간선 중 최솟값을 가장 빠르게 찾아내는" 문제를 해결하기 위해, 우리는 앞서 배운 바있는 강력한 도구인 우선순위 큐(Priority Queue)를 사용하게 된다.

우선순위 큐는 가장 작은 (혹은 가장 큰) 원소가 항상 맨 위에 위치하도록 자동 정렬되는 자료구조이다.

따라서 우리가 할 일은 후보 간선들을 우선순위 큐에 전부 넣어두고, 필요할 때마다 맨 위의 최솟값만 쏙쏙 뽑아 쓰기만 하면 된다!

Prim 알고리즘 구현 (feat. 우선순위 큐)

우선순위 큐를 사용하면 위에서 설명한 distance와 parent 배열을 직접 관리할 필요 없이, 이 정보들을 큐에 넣는 (가중치, 부모, 자식) 튜플로 한번에 관리할 수 있다.

distance → 간선 정보 튜플에서 가중치 부분
parent → 부모 정점
"최소 distance 찾기" → 우선순위 큐에서 heappop 하기

이제 이 아이디어를 바탕으로 실제 코드를 살펴보자!

초기화 작업

import heapq

# G: 그래프, start_node: 시작 정점
def prim(G, start_node):
    # 'visited' 정보: MST에 포함된 정점을 기록
    visited = {start_node}
    
    # MST 결과 및 총 가중치를 저장할 변수들
    MST = []
    total_weight = 0
    
    # 우선순위 큐: (가중치, 부모, 자식) 형태로 간선 정보를 저장
    # 가중치가 가장 낮은 간선이 항상 우선적으로 추출됨
    priority_queue = [
        (weight, start_node, neighbor) 
        for neighbor, weight in G[start_node].items()
    ]
    heapq.heapify(priority_queue) # 리스트를 우선순위 큐로 변환
    

# 주어진 그래프
graph = {
    1: { 2: 2, 4: 1, 5: 4 },
    2: { 1: 2, 3: 3, 4: 3, 6: 7 },
    3: { 2: 3, 4: 5, 6: 8 },
    4: { 1: 1, 2: 3, 3: 5, 5: 9 },
    5: { 1: 4, 4: 9 },
    6: { 2: 7, 3: 8 }
}

시작 정점을 visited에 추가
시작 정점과 연결된 모든 간선 정보를 (가중치, 부모, 자식) 형태로 우선순위 큐에 추가
이 때 가중치가 낮은 간선이 높은 우선순위를 갖도록 맨 앞 요소로 설정

MST 구축 루프: 최소 비용 간선을 뽑아 트리를 키워나가기

현재 우선순위 큐에는 시작 정점에 연결된 간선들이 담겨있는 상태이다.

이제 큐에서 가장 저렴한 간선을 계속 뽑아내면서 MST를 키워나가면 된다.

모든 정점이 연결될 때까지(= MST 간선 수가 n-1이 될 때까지) 이 과정을 반복하면 된다.

    # MST가 (정점의 개수 - 1)개의 간선을 가질 때까지 반복
    while priority_queue and len(MST) < len(G) - 1:
        
        # 1. 현재 큐에서 가장 가중치가 낮은 간선(최소 비용 간선)을 꺼냄
        weight, u, v = heapq.heappop(priority_queue)
        
        # 2. 이미 방문한 정점인지 확인 (사이클 방지)
        # 만약 꺼낸 간선이 연결하려는 정점(v)이 이미 MST에 포함되어 있다면,
        # 이 간선을 추가하면 사이클이 생기므로 무시하고 다음으로 넘어감
        if v in visited:
            continue
            
        # 3. 새로운 정점과 간선을 MST에 추가
        # 이 간선은 사이클을 만들지 않는, 현재로서는 최적의 선택
        visited.add(v)            # 'v'를 이제 MST의 일부로 선언
        MST.append((u, v, weight)) # MST 결과 리스트에 (부모, 자식, 가중치) 간선을 추가
        total_weight += weight
        
        # 4. 새로 추가된 정점(v)에 연결된 간선들을 다시 큐에 추가
        # 이제 우리의 MST 영역이 넓어졌으니, 새로운 후보 간선들을 탐색해야 함
        for neighbor, next_weight in G[v].items():
            # 단, 이미 MST에 포함된 정점으로 가는 간선은 추가할 필요 X
            if neighbor not in visited:
                heapq.heappush(priority_queue, (next_weight, v, neighbor))
                
    # 5. 모든 과정이 끝나면 완성된 MST와 총 가중치를 반환
    return MST, total_weight

가장 저렴한 길 찾기 (heappop)

heapq.heappop(priority_queue) 코드는 현재 큐에 있는 모든 후보 간선 중에서 가중치가 가장 낮은 간선을 자동으로 꺼내준다.

이로인해 Prim 알고리즘의 핵심인 "가장 가중치가 작은 간선 선택" 과정을 $O(logE)$라는 빠른 속도로 처리가 가능해진다!

꺼내진 (weight, u, v) 튜플은 u를 부모로 하여 v로 가는, 가장 저렴한 간선이라는 의미를 가진다.
사이클 확인 (if v in visited:)

큐 안에는 같은 목적지(v)로 가는 여러 경로가 있을 수 있다 (ex: A->C 비용 10, B->C 비용 5).

하지만 우선순위 큐 덕분에 우리는 항상 비용이 더 저렴한 (5, B, C) 간선을 먼저 처리하게 된다.

이 간선이 처리되면 C는 visited에 추가되고, 나중에 큐에 남아있던 비효율적인 간선 (10, A, C)가 꺼내지더라도,

조건문 if C in visited:에 걸려 자연스럽게 무시된다.

이 한 줄이 불필요한 연결(사이클)을 완벽하게 막아주는 것이다.
트리 확장

사이클 검사를 통과했다면, 이제 실제로 MST에 포함시키게 된다.

새로운 정점 v를 visited 집합에 추가해주고 (u, v, weight) 간선을 MST 결과 리스트에 저장한다.
새로운 후보 탐색

새로운 정점 v가 MST에 합류했으니 이제 시야가 더 넓어졌다.

v에 연결된 다른 길들을 탐색하며, 아직 방문안한 정점으로 가는 간선들을 새로운 후보로 우선순위 큐에 추가한다. 이로써 큐는 이 새로운 후보들까지 포함해서 다음 단계의 최적의 간선을 찾아줄 준비를 마치게 됐다!

위의 1~4번 과정이 (n-1)개의 간선이 선택될 때까지 반복되면, 모든 정점을 최소 비용으로 연결하는 완벽한 MST가 탄생하게 된다!

import heapq

# G: 그래프, start_node: 시작 정점
def prim(G, start_node):
    # 'visited' 정보: MST에 포함된 정점을 기록
    visited = {start_node}
    
    # MST 결과 및 총 가중치를 저장할 변수들
    MST = []
    total_weight = 0
    
    # 우선순위 큐: (가중치, 부모, 자식) 형태로 간선 정보를 저장
    # 가중치가 가장 낮은 간선이 항상 우선적으로 추출됨
    priority_queue = [
        (weight, start_node, neighbor) 
        for neighbor, weight in G[start_node].items()
    ]
    heapq.heapify(priority_queue) # 리스트를 우선순위 큐로 변환
    
    # MST가 (정점의 개수 - 1)개의 간선을 가질 때까지 반복
    while priority_queue and len(MST) < len(G) - 1:
        
        # 1. 현재 큐에서 가장 가중치가 낮은 간선(최소 비용 간선)을 꺼냄
        weight, u, v = heapq.heappop(priority_queue)
        
        # 2. 이미 방문한 정점인지 확인 (사이클 방지)
        # 만약 꺼낸 간선이 연결하려는 정점(v)이 이미 MST에 포함되어 있다면,
        # 이 간선을 추가하면 사이클이 생기므로 무시하고 다음으로 넘어감
        if v in visited:
            continue
            
        # 3. 새로운 정점과 간선을 MST에 추가
        # 이 간선은 사이클을 만들지 않는, 현재로서는 최적의 선택
        visited.add(v)            # 'v'를 이제 MST의 일부로 선언
        MST.append((u, v, weight)) # MST 결과 리스트에 (부모, 자식, 가중치) 간선을 추가
        total_weight += weight
        
        # 4. 새로 추가된 정점(v)에 연결된 간선들을 다시 큐에 추가
        # 이제 우리의 MST 영역이 넓어졌으니, 새로운 후보 간선들을 탐색해야 함
        for neighbor, next_weight in G[v].items():
            # 단, 이미 MST에 포함된 정점으로 가는 간선은 추가할 필요 X
            if neighbor not in visited:
                heapq.heappush(priority_queue, (next_weight, v, neighbor))
                
    # 5. 모든 과정이 끝나면 완성된 MST와 총 가중치를 반환
    return MST, total_weight

graph = {
    1: { 2: 2, 4: 1, 5: 4 },
    2: { 1: 2, 3: 3, 4: 3, 6: 7 },
    3: { 2: 3, 4: 5, 6: 8 },
    4: { 1: 1, 2: 3, 3: 5, 5: 9 },
    5: { 1: 4, 4: 9 },
    6: { 2: 7, 3: 8 }
}

a = prim(graph, 4) # ([(4, 1, 1), (1, 2, 2), (2, 3, 3), (1, 5, 4), (2, 6, 7)], 17)
print(a)

Prim 알고리즘 성능 분석: 시간 복잡도 ⏱️

Prim 알고리즘의 효율성, 즉 시간 복잡도는 어떤 도구(자료구조)를 사용해 구현하느냐에 따라 크게 달라진다.

단순 배열/리스트 구현: O(V^2) 가장 직관적인 방법은 매 단계마다 'MST에 포함되지 않은 정점'들을 모두 확인하여 가장 distance가 짧은 정점을 찾는 것이다. 이는 마치 상점의 모든 물건을 하나하나 다 살펴보고 가장 싼 물건을 찾는 것과 같다. 이 과정을 (V-1)번 반복해야 하므로, 총 시간 복잡도는 O(V^2) (V는 정점의 개수)가 된다. 그래프가 작을 땐 괜찮지만, 정점이 많아지면 속도가 급격히 느려진다.
우리가 사용한 우선순위 큐 구현: O(E log V) 우선순위 큐를 사용하면 "가장 가중치가 낮은 간선"을 O(log V)라는 아주 빠른 속도로 찾아낼 수 있다. 모든 간선을 최대 한 번씩 큐에 넣고 빼는 과정을 거치므로, 전체 시간 복잡도는 O(E log V) (E는 간선의 개수)로 크게 향상된다.
(심화) 피보나치 힙 구현: O(E + V log V)

지금까지 우리는 하나의 점에서 시작해 점차 자신의 세력을 넓혀가며 MST를 구축하는 Prim 알고리즘에 대해 알아봤다.

Prim 알고리즘은 아래와 같은 특징을 가진다.

시작점이 필요하며, 연결된 하나의 그래프에 대한 MST를 만든다.

만약 처음부터 그래프가 여러 조각으로 나뉘어 있었다면, Prim 알고리즘은 우리가 출발한 지점이 속한 조각의 MST만 만들어낼 것이다.

그렇다면 애초에 그래프가 여러 조각으로 나뉘어 있을 때나, 혹은 꼭 한 지점에서 시작하지 않고 숲(forest) 전체를 아우르는 MST를 만드는 다른 방법은 없을까? 🤔

다음 포스팅에서는 바로 그 질문에 대한 답, 크루스칼(Kruskal) 알고리즘과 그의 핵심 파트너 Union-Find 자료구조에 대해 알아보자! 👋

참고 자료

snu open courseware: Introduction to Data Structures

https://www.w3schools.com/dsa/dsa_algo_mst_prim.php