12.10 최소 신장 트리 알고리즘

12.10 최소 신장 트리 알고리즘

1. 최소 신장 트리의 개요

최소 신장 트리(Minimum Spanning Tree, MST)는 가중치 무방향 연결 그래프에서 모든 노드를 연결하면서 엣지 가중치의 합이 최소가 되는 트리이다. MST는 네트워크 설계, 클러스터링, 회로 설계, 통신 네트워크 등 다양한 응용에서 핵심적인 역할을 한다. 로봇공학에서는 다중 로봇의 통신 네트워크 설계, 환경 분할, 클러스터링 기반 경로 계획 등에 활용된다. 본 절에서는 MST의 정의, 성질, 그리고 두 가지 주요 알고리즘인 Kruskal 알고리즘과 Prim 알고리즘을 다룬다.

2. 신장 트리

2.1 정의

연결 그래프 G = (V, E)의 신장 트리(spanning tree)는 다음을 만족하는 부분 그래프 T = (V, E_T)이다.

  • 모든 노드를 포함한다 (T는 신장).
  • 트리이다 (연결되어 있고 사이클이 없다).

2.2 신장 트리의 성질

신장 트리는 다음의 성질을 가진다.

  • 정확히 |V| - 1개의 엣지를 가진다.
  • 임의의 두 노드 사이에 유일한 경로가 존재한다.
  • 한 엣지를 제거하면 그래프가 분리된다.
  • 한 엣지를 추가하면 사이클이 형성된다.

2.3 신장 트리의 다양성

연결 그래프는 일반적으로 여러 개의 신장 트리를 가진다. 트리의 수는 그래프의 구조에 의존한다.

3. 최소 신장 트리

3.1 정의

가중치 그래프의 최소 신장 트리는 신장 트리 중 엣지 가중치의 합이 최소인 것이다.

\text{MST}(G) = \arg\min_{T \in ST(G)}\sum_{e \in E_T}w(e)

여기서 ST(G)는 G의 모든 신장 트리의 집합이다.

3.2 MST의 유일성

엣지 가중치가 모두 다르면 MST는 유일하다. 같은 가중치가 있으면 여러 MST가 존재할 수 있다.

4. MST의 응용

4.1 네트워크 설계

전기 회로, 통신 네트워크, 도로 시스템 등의 설계에서 모든 노드를 최소 비용으로 연결하는 문제이다.

4.2 클러스터링

데이터 클러스터링에서 MST를 사용한 알고리즘이 있다. MST의 가장 큰 엣지를 제거하여 클러스터를 분리한다.

4.3 이미지 분할

이미지의 픽셀을 노드로 보고, 인접 픽셀의 차이를 가중치로 한 그래프의 MST를 사용하여 이미지를 분할한다.

4.4 회로 설계

VLSI 회로 설계에서 모든 컴포넌트를 최소 길이의 와이어로 연결하는 문제이다.

5. MST의 핵심 성질

5.1 절단 성질

그래프의 절단(cut)은 노드를 두 부분 집합으로 나누는 것이다. 절단을 가로지르는 엣지(cut edge) 중 가중치가 가장 작은 엣지는 어떤 MST에 포함된다.

이를 절단 성질(cut property)이라 한다.

5.2 사이클 성질

그래프의 사이클에서 가중치가 가장 큰 엣지는 어떤 MST에도 포함되지 않는다.

이를 사이클 성질(cycle property)이라 한다.

이 두 성질이 MST 알고리즘 설계의 기초이다.

6. Kruskal 알고리즘

6.1 개요

Kruskal 알고리즘은 1956년 조셉 크루스칼(Joseph Kruskal)이 제안한 MST 알고리즘이다. 엣지를 가중치 순으로 정렬한 후, 사이클을 만들지 않는 엣지를 차례로 추가한다.

6.2 알고리즘

Kruskal(G):
    A = empty set  // MST의 엣지 집합
    
    // 모든 엣지를 가중치 순으로 정렬
    sort edges of E in non-decreasing order by weight
    
    // Union-Find 자료 구조 초기화
    for each node v in V:
        MAKE_SET(v)
    
    // 엣지를 순서대로 처리
    for each edge (u, v) in sorted edges:
        if FIND_SET(u) != FIND_SET(v):
            A = A ∪ {(u, v)}
            UNION(u, v)
    
    return A

6.3 Union-Find 자료 구조

Kruskal 알고리즘의 효율성은 Union-Find(Disjoint Set Union) 자료 구조에 의존한다. Union-Find는 두 가지 연산을 효율적으로 지원한다.

  • MAKE_SET(x): 원소 x를 포함하는 새 집합을 생성한다.
  • FIND_SET(x): x가 속한 집합의 대표 원소를 반환한다.
  • UNION(x, y): x와 y가 속한 두 집합을 합친다.

6.4 Union-Find의 효율성

Union-Find는 경로 압축(path compression)과 랭크 기반 합집합(union by rank)으로 거의 상수 시간(분할 상환)으로 동작한다. 정확한 분석은 아커만 함수의 역과 관련된다.

6.5 시간 복잡도

Kruskal 알고리즘의 시간 복잡도는 O(|E|\log|E|)이며, 주로 엣지 정렬에 시간이 소요된다. Union-Find 연산은 거의 상수 시간이다.

7. Prim 알고리즘

7.1 개요

Prim 알고리즘은 1957년 로버트 프림(Robert Prim)이 제안한 MST 알고리즘이며, 더 일찍 1930년 보르프카(Borůvka)와 1957년 야르닉(Jarník)도 유사한 알고리즘을 제안하였다. Prim 알고리즘은 한 노드에서 시작하여 트리를 확장한다.

7.2 알고리즘

Prim(G, r):
    for each node v in V:
        v.key = ∞
        v.parent = None
    r.key = 0
    
    Q = priority queue with all nodes (key = key value)
    
    while Q is not empty:
        u = Q.extract_min()
        for each neighbor v of u:
            if v in Q and w(u, v) < v.key:
                v.parent = u
                v.key = w(u, v)
                Q.decrease_key(v, v.key)
    
    return MST formed by parent pointers

7.3 단계별 동작

  1. 시작 노드를 선택하고 키를 0으로, 다른 노드의 키를 무한대로 설정한다.
  2. 모든 노드를 우선순위 큐에 추가한다.
  3. 큐가 빌 때까지 다음을 반복한다.
  • 가장 작은 키를 가진 노드를 추출한다.
  • 그 노드의 이웃들의 키를 갱신한다.

7.4 시간 복잡도

Prim 알고리즘의 시간 복잡도는 우선순위 큐의 구현에 의존한다.

우선순위 큐시간 복잡도
단순 배열O(\vert V\vert^2)
이진 힙O((\vert V\vert + \vert E\vert)\log\vert V\vert)
피보나치 힙O(\vert V\vert\log\vert V\vert + \vert E\vert)

8. Kruskal과 Prim의 비교

8.1 알고리즘적 차이

측면KruskalPrim
접근 방식엣지 중심노드 중심
자료 구조Union-Find우선순위 큐
시작빈 집합에서 시작한 노드에서 시작
정렬모든 엣지 정렬우선순위 큐 사용

8.2 시간 복잡도

알고리즘시간 복잡도
KruskalO(\vert E\vert\log\vert E\vert)
Prim (이진 힙)O((\vert V\vert + \vert E\vert)\log\vert V\vert)
Prim (피보나치 힙)O(\vert V\vert\log\vert V\vert + \vert E\vert)

희소 그래프에서는 Kruskal이, 밀집 그래프에서는 Prim이 더 효율적일 수 있다.

8.3 응용 차이

  • 분산 환경에서는 Kruskal이 더 자연스럽다.
  • 그래프가 점진적으로 확장되는 경우 Prim이 적합하다.

9. Borůvka 알고리즘

9.1 개요

Borůvka 알고리즘은 1926년 체코의 수학자 오타카르 보르프카(Otakar Borůvka)가 제안한 가장 오래된 MST 알고리즘이다. 병렬화에 적합하다.

9.2 알고리즘

Boruvka(G):
    A = empty set
    components = each node forms a singleton component
    
    while |components| > 1:
        for each component C:
            find the minimum weight edge from C to another component
        add all these edges to A (avoiding duplicates)
        update components
    
    return A

9.3 특성

Borůvka 알고리즘은 각 단계에서 컴포넌트의 수를 절반 이하로 줄인다. 따라서 O(\log|V|) 단계가 필요하며, 병렬 처리에 적합하다.

10. Python 구현

10.1 Kruskal 알고리즘

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])
    uf = UnionFind(n)
    mst = []
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
    return mst

10.2 Prim 알고리즘

import heapq

def prim(graph, start):
    visited = {start}
    edges = [(w, start, v) for v, w in graph[start].items()]
    heapq.heapify(edges)
    mst = []
    
    while edges:
        w, u, v = heapq.heappop(edges)
        if v in visited:
            continue
        visited.add(v)
        mst.append((u, v, w))
        
        for neighbor, weight in graph[v].items():
            if neighbor not in visited:
                heapq.heappush(edges, (weight, v, neighbor))
    
    return mst

11. MST의 변형

11.1 최대 신장 트리

엣지 가중치를 음수로 변환하면 MST 알고리즘으로 최대 신장 트리(maximum spanning tree)를 찾을 수 있다.

11.2 직경 제한 신장 트리

신장 트리의 직경(가장 긴 경로)에 제한이 있는 MST 변형이다. NP-hard 문제이다.

11.3 신장 부분 그래프

정확히 트리가 아니라 더 일반적인 부분 그래프(예: k-edge connected)를 찾는 문제도 있다.

11.4 Steiner 트리

Steiner 트리 문제는 일부 노드(터미널)만 연결하는 최소 가중치 트리를 찾는다. MST의 일반화이며 NP-hard이다.

12. MST의 응용

12.1 네트워크 설계

전기 회로, 통신 네트워크, 도로 등의 설계에서 모든 거점을 최소 비용으로 연결하는 문제이다. 직접 MST 알고리즘이 적용된다.

12.2 클러스터링

데이터 점들의 MST를 만든 후, 가장 큰 엣지를 제거하면 클러스터가 분리된다. 단일 연결 클러스터링(single-linkage clustering)이 이 방법을 사용한다.

12.3 이미지 분할

이미지의 픽셀을 노드로 한 그래프의 MST를 사용하여 이미지를 분할한다. Felzenszwalb 알고리즘이 대표적이다.

12.4 컴퓨터 비전

특징점 매칭, 객체 추적 등에 MST가 활용된다.

13. 로봇공학에서의 응용

13.1 다중 로봇 통신 네트워크

여러 로봇이 통신할 때 모든 로봇을 연결하는 최소 비용 네트워크를 MST로 설계할 수 있다.

13.2 환경 분할

환경을 영역으로 분할하는 데 MST가 사용된다. 로봇이 영역을 순회하는 경로 계획에 활용된다.

13.3 클러스터링 기반 경로 계획

로봇이 여러 목표를 방문할 때, 목표를 클러스터로 묶고 클러스터 내에서 경로를 계획한다. MST가 클러스터링에 사용된다.

13.4 군집 로봇

군집 로봇의 통신 토폴로지나 협력 작업의 분할에 MST가 활용된다.

13.5 환경 탐색

미지의 환경을 탐색할 때 발견된 노드들의 MST를 유지하면서 효율적인 탐색이 가능하다.

14. 응용 예시: 다중 로봇 통신

10대의 드론이 협력 비행을 할 때, 모든 드론이 서로 연결되어야 한다. 통신 비용(거리, 신호 강도)을 가중치로 한 완전 그래프의 MST가 최소 비용 통신 네트워크를 제공한다.

def design_communication_network(robot_positions):
    n = len(robot_positions)
    edges = []
    for i in range(n):
        for j in range(i+1, n):
            dist = euclidean_distance(robot_positions[i], robot_positions[j])
            edges.append((i, j, dist))
    return kruskal(n, edges)

15. 응용 예시: 환경 클러스터링

로봇이 큰 환경에서 작업할 때, 환경을 작은 클러스터로 나누어 효율적으로 처리한다. 각 셀의 위치를 노드로 한 그래프의 MST를 사용한 클러스터링이 자연스럽다.

16. 응용 예시: TSP의 휴리스틱

여행하는 외판원 문제(Traveling Salesman Problem, TSP)는 모든 도시를 한 번씩 방문하는 최소 비용 경로를 찾는다. MST는 TSP의 하한을 제공하며, MST 기반 휴리스틱(예: Christofides 알고리즘)이 사용된다.

17. 응용 예시: 회로 설계

VLSI 회로의 컴포넌트를 와이어로 연결할 때 MST가 와이어의 총 길이를 최소화한다. Steiner 트리는 더 정교한 일반화이다.

18. MST의 라이브러리 지원

18.1 NetworkX

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 0.5), (1, 3, 1.2), (2, 3, 0.3), (2, 4, 1.5)])

# Kruskal
mst = nx.minimum_spanning_tree(G, algorithm='kruskal')

# Prim
mst = nx.minimum_spanning_tree(G, algorithm='prim')

# 엣지만 반환
edges = nx.minimum_spanning_edges(G)

18.2 다른 라이브러리

  • igraph
  • Boost Graph Library
  • graph-tool
  • SciPy의 sparse graph 모듈

19. 분산 MST

19.1 분산 환경

여러 컴퓨터에서 그래프가 분산되어 저장된 경우 분산 MST 알고리즘이 필요하다.

19.2 Gallager-Humblet-Spira 알고리즘

GHS 알고리즘은 분산 환경에서 MST를 계산하는 고전적 알고리즘이다.

19.3 응용

분산 MST는 통신 네트워크, 분산 시스템, 다중 로봇 시스템 등에서 활용된다.

20. MST의 일반화

20.1 가중치가 없는 경우

가중치가 없는 그래프에서 신장 트리는 단순히 사이클이 없는 연결 부분 그래프이다. BFS나 DFS로 만들 수 있다.

20.2 방향 그래프

방향 그래프에서는 신장 분기수형도(spanning arborescence)라는 개념이 있다. 이는 한 루트에서 다른 모든 노드로의 방향 트리이다. 최소 신장 분기수형도는 Edmonds 알고리즘으로 계산된다.

20.3 행렬 트리 정리

키르히호프의 행렬 트리 정리(matrix tree theorem)는 그래프의 신장 트리의 수를 라플라시안 행렬의 행렬식으로 계산한다.

21. 학습의 가치

최소 신장 트리 알고리즘을 이해하는 것은 다음과 같은 이점을 제공한다.

  • 그래프 이론의 또 다른 핵심 알고리즘을 익힌다.
  • Union-Find와 우선순위 큐의 활용을 학습한다.
  • 그리디 알고리즘 설계의 표본을 익힌다.
  • 네트워크 설계와 클러스터링의 기본을 이해한다.
  • 다양한 응용에 적용할 수 있다.

22. 학습 권장사항

22.1 직접 구현

Kruskal과 Prim 알고리즘을 모두 직접 구현해 본다. Union-Find 자료 구조도 함께 구현한다.

22.2 시각화

알고리즘의 단계별 시각화는 이해에 매우 유용하다. 각 단계에서 어떤 엣지가 추가되는지 볼 수 있다.

22.3 응용 학습

네트워크 설계, 클러스터링, 이미지 분할 등의 응용에 적용해 본다.

22.4 변형 학습

최대 신장 트리, Steiner 트리, 분산 MST 등의 변형을 학습한다.

23. 본 절의 의의

본 절은 최소 신장 트리 알고리즘을 자세히 다루었다. MST는 그래프 이론의 핵심 개념이며, 네트워크 설계, 클러스터링 등 다양한 응용에서 활용된다. Kruskal과 Prim 알고리즘은 모두 그리디 알고리즘 설계의 우수한 예시이며, 다른 알고리즘 학습의 기초가 된다.

24. 참고 문헌

  • Kruskal, J. B. (1956). “On the shortest spanning subtree of a graph and the traveling salesman problem.” Proceedings of the American Mathematical Society, 7(1), 48–50.
  • Prim, R. C. (1957). “Shortest connection networks and some generalizations.” Bell System Technical Journal, 36(6), 1389–1401.
  • Borůvka, O. (1926). “O jistém problému minimálním.” Práce Mor. Přírodověd. Spol. v Brně, 3, 37–58.
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Tarjan, R. E. (1983). Data Structures and Network Algorithms. SIAM.
  • Gabow, H. N. (1976). “An efficient implementation of Edmonds’ algorithm for maximum matching on graphs.” Journal of the ACM, 23(2), 221–234.

version: 1.0