로그인회원가입
[알고리즘] 최소신장트리

2026.07.17. 22:12

최소 신장 트리(MST, Minimum Spanning Tree)는 가중치가 있는 무방향 연결 그래프에서 모든 정점을 연결하면서 간선의 가중치 합이 최소인 트리를 말합니다. (코딩일지)

조건

최소 신장 트리는 다음 조건을 만족해야 합니다.

  • 모든 정점을 포함한다.

  • 모든 정점이 연결되어 있다.

  • 사이클(Cycle)이 존재하지 않는다.

  • 간선의 개수는 정점 수 - 1(V-1)이다.

  • 선택된 간선의 가중치 합이 최소이다. (코딩일지)

예시

다음과 같은 그래프가 있다고 가정해 보겠습니다.

A --1-- B
|      / |
4    2   5
|   /    |
C --3-- D

가능한 최소 신장 트리는 다음과 같습니다.

  • A-B (1)

  • B-D (2)

  • C-D (3)

총 가중치 = 1 + 2 + 3 = 6

대표 알고리즘

  1. 크루스칼(Kruskal) 알고리즘

    • 간선을 가중치 순으로 정렬한다.

    • 가장 작은 간선부터 선택한다.

    • 사이클이 생기면 선택하지 않는다.

    • 주로 Union-Find(Disjoint Set) 자료구조를 사용한다.

    시간 복잡도: (O(E \log E))

  2. 프림(Prim) 알고리즘

    • 임의의 정점에서 시작한다.

    • 현재 트리와 연결되는 가장 작은 가중치의 간선을 선택하며 확장한다.

    • 우선순위 큐(힙)를 사용하면 효율적이다.

    시간 복잡도: (O(E \log V))

활용 분야

  • 도로 및 철도 건설 비용 최소화

  • 전력망 설계

  • 통신망 구축

  • 컴퓨터 네트워크 연결

  • 배관 및 케이블 설치 비용 최소화 (AngelPlayer`s Diary)

면접이나 알고리즘 시험에서는 크루스칼과 프림의 차이점, 시간 복잡도, 그리고 Union-Find를 이용한 크루스칼 구현이 자주 출제됩니다.

목록