목표

• MST가 왜 필요한가를 이해한다.
• MST를 이해한다.
• MST를 구현하는 알고리즘을 이해한다.
  • Generic
    • Kruskal's Alogrithm
    • Prim's Algorithm
• MST를 구현해본다.

MST의 필요성

• 네트워크 예
  어떤 네트워크 망을 구축하자고 한다면 모든 네트워크 포인트는 연결되어야 함
  네트워크 포인트 간 양방향 연결이 이루어지면 되는데 회선의 수가 적을수록 비용 효율적임
  따라서 각 노드를 모두 양방향(무방향) 연결하면서 최소한의 회선(Edge)을 만들 수 있는 방법을 찾아야 함

이에 따라 MST의 목적은 무방향 가중치 그래프에서 최소 Edge를 구현하기 위한 방법이 MST임.

MST

• 무방향 가중치 그래프에서 적용되는 최소 비용(가중치가 낮은) 간선 트리를 형성하기 위한 알고리즘
• $n$개 정점을 가지는 트리는 $n-1$개 간선을 가져야 한다.(모든 노드를 거쳐야하기 때문)
  • 트리
    acyclic connected andirected graph
    사이클 없이 연결된 무방향 그래프를 트리라고 한다.
    이진 트리의 경우 루트가 존재하는 rooted tree로 구분 가능
• MST는 하나의 그래프 내에 여러 개가 존재할 수 있다.

Safe Edge

• MST를 구성한 에지가 다른 에지가 추가 되었을 때 MST에 영향이 없다면 그 에지는 안전한 에지라고 한다.
  붉은 에지들은 MST를 구성한 파란 에지에 영향을 주지 않는다.

Cut

• 정점 집합 S와 나머지 V-S

Cross

• 두 집합을 교차

Respect

• 서로 다른 에지 집합들이 Cross 되지 않을 때 이는 Cut을 Respect한다고 함

정리

MST를 구현하는 공통 알고리즘

1. 처음 하나의 집합을 선택한다.
2. 집합 $A$에 대해 '안전'한 edge를 탐색하여 $A$에 더한다.
3. edge 개수가 $n-1$이 될 때까지 2번을 반복한다.

Kruskal's Algorithm

• 간선 선택 기반
• Greedy(탐욕적인)를 사용하여 모든 간선을 확인하고 추가한다.

구현법

1. edge들은 가중치의 오름차순 정렬
2. 정렬된 edge 중 가중치가 제일 낮은 edge부터 하나씩 선택 후 union
   만약 선택하는 edge와 선택된 edge가 Cycle을 이룬다면 선택 안함
3. edge가 $n-1$개 선택될 때까지 반복

왜 Kruskal's Algorithm을 쓰면 MST를 만들 수 있을까?

• kruskal이 진행 중에 cycle이 형성되지 않은 정점 $u$를 가진 간선집합 $V-S$와
  정점 $v$를 가진 간선집합 $S$가 있다면 이 둘은 연결되지 않았다.
• 정점 $u$와 정점$v$는 연결되지 않았기에 이 간선집합의 어떤 부분을 연결해도 Cycle은 형성되지 않는다 즉 간선집합 $S$와 $V-S$는 안전한 edge를 가진다.

Kruskal Algorithm 따로 정리

Prim's Algorithm

• 정점 선택 기반
• 최소 힙을 사용해서 가중치를 판단하기때문에 MST를 구현할 수 있음

구현법

1. 최소 힙에서 가중치가 가장 작은 정점을 시작 정점으로 선택
2. 인접 정점 중 가중치가 가장 낮은 간선을 선택
   만약 선택하는 edge와 선택된 edge가 Cycle을 이룬다면 선택 안함
3. edge가 n-1 될 때까지 반복

Prim's Algorithm 따로 정리

참고

dinohee blog
권오흠 MST
ratsgo blog
명지대학교 알고리즘
위키