최소 신장 트리 MST

최소 신장 트리(Minimum Spanning Tree)는
모든 노드가 최소한의 비용,간선으로 연결된 트리를 의미합니다.
여기서 비용(cost)은 두 노드간에 연결된 간선의 길이를 말합니다.
예를 들어, 위 그림에서는 A<->C는 3이다.

신장 트리

신장 트리는 Spanning Tree라고 하며
모든 노드가 최소한의 간선 수로 연결되어있는 트리를 말한다.

위에 예시 그림을 기준으로 A-C-B-D-E-F가 전부 신장 트리로 이어져있다.
신장 트리의 경우 노드의 갯수가 n일 때 간선의 갯수는 n-1이다.

MST 성립 조건

1. 사이클이 발생하면 안 된다.
2. 간선의 수가 신장 트리 조건을 만족해야한다.

MST를 구하는 알고리즘

MST를 구하는 알고리즘은 대표적으로 2가지가 있다.
1. 크루스칼 알고리즘 (Kruskal Algorithm)
2. 프림 알고리즘 (Prim Algorithm)

크루스칼 알고리즘

Kruskal Algorithm은 간선을 기준으로 최소 신장 트리를 구한다.

핵심은 간선의 비용을 오름차순으로 정렬해서
최소 비용인 간선부터 연결하면서 연결하는 중간에
union-find 알고리즘을 사용해서 MST 성립 조건을 확인한다.
사이클이 생기는지

사이클 생성 판단 기준

간선을 연결했을 때 사이클이 생기는 지 판단하는 기준은
두 노드의 루트 노드를 각각 구하고
각각의 루트 노드가 다른 경우
두 노드가 연결되었을 때 사이클이 생기지 않는다.

프림 알고리즘

Prim's algorithm은 노드를 기준으로 최소 신장 트리를 구한다.

맨 처음 노드를 정해 연결된 간선 중에 최소 비용의 간선을 선택에 연결한다.
연결된 두 노드를 한 덩어리로 보고 아직 연결되지 않은 간선 중에
최소 비용의 간선을 연결한다.이를 반복한다.