[Week03] 최소 신장 트리

가중치 무방향 연결 그래프에서 모든 정점을 이을 수 있는 최소 가중치인 트리 찾기

특징 및 성질

• 가중치가 모두 다르면 MST는 유일하다
• 최단경로 트리와는 다르다. MST는 전체 합 최소, 최단 경로 트리는 한 출발점에서의 거리 최소

대표 알고리즘 2개

Kruskal algorithm

간선 정렬과 유니온 파인드 2개를 결합한 알고리즘

복잡도 : O(E logE) 희소 그래프에 강하다

Prim algorithm

최소 힙과 인접리스트로 구현

간선리스트만 있는 경우는 Kruskal, 인접 리스트가 있고 시작 정점이 상관 없으면 Prim()

중요 포인트

Cut Property

어떤 컷을 가로지르는 최소 가중치 간선은 MST에 포함되어야 한다 (가로지르면 안된다? 오타로 보임, 원래는 포함)

Cycle Property

사이클에서 가장 무거운 간선은 MST에 포함될 수 없다.

MST 유일성

모든 간선 가중치가 서로 다르면 단 하나의 MST만 존재한다

간선 리스트 예시

단순 간선의 모음

바로 정렬해서 Kruskal에 적용

Prim을 쓰려면 간선 리스트를 인접리스트로 변경 필요

형태: u v w (정점 u, 정점 v, 가중치 w) N줄

• 보통 M = 간선 개수 주어지고, 이어서 M줄 간선 나열.
• 예:

3 3 1 2 1 2 3 2 1 3 3

인접 리스트 예시

Prim을 바로 적용 가능

Kruskal을 사용하려면 다시 모든 간선을 한 리스트로 뽑아야 함

형태: 각 노드마다 연결된 노드 정보 제공.

예:

5 0: (1,1), (2,3) 1: (0,1), (2,3), (3,6) ...

활용

MST는 모든 노드를 연결하면서의 비용 최소화하는 것이 목표, 주로 인프라 설계 및 네트워크 최적화

• 전력망, 수도관, 통신망 설계
• 네트워크 케이블 배치
• 군집 분석