프림(Prim)과 크루스칼(Kruskal) 알고리즘

▶신장 트리 (Spanning Tree)

---

 그래프의 모든 정점을 연결한 Tree를 말한다. 하나의 그래프에서 신장 트리는 여러 형태가 나올 수 있다.

▶최소 신장 트리 (MST : Minimum Spanning Tree)

---

 다음과 같은 조건을 만족하는 신장 트리를 말한다.

1. 간선의 가중치 합이 최소이다.

2. 사이클이 존재하지 않는다.

3. 모든 정점이 연결되어야 한다. (N개의 정점은 N-1개의 간선으로 연결됨)

하나의 그래프에서 MST도 역시 여러 형태가 나올 수 있다.

MST를 구하는 대표적인 알고리즘으로 프림 알고리즘과 크루스칼 알고리즘이 있다.

▶프림 알고리즘 (Prim algorithm)

---

 시작 정점을 기준으로 가중치가 가장 작은 간선과 연결된 정점을 선택하며 트리를 확장시켜나가는 방법이다.

트리 집합에 포함된 정점이 X 개가 되면 X 개의 정점과 아직 선택되지 않은 정점들 사이에 연결된 간선들 중 가중치가 가장 작은 것을 찾고 그와 연결된 정점을 트리 집합에 포함시킨다. 하나의 연결 그래프에 대하여 모든 정점이 트리 집합에 포함될 때까지 반복하도록 구현한다.

 우선순위 큐 자료구조와 인접 리스트를 사용하면 우선순위 큐의 push/pop 연산에 O(logV)의 시간이 걸리고, 모든 간선을 확인하기 위해 우선순위 큐에 간선을 push하는 연산이 E번, 확인을 위해 pop하는 연산이 최대 E번 수행되므로 O(E)가 된다. 따라서, 전체적으로 O(ElogV)의 시간이 걸린다. 

간선의 개수에 비해 정점의 개수가 적은 경우 유리한 알고리즘이다. 

▶크루스칼 알고리즘 (Kruskal algorithm)

---

 모든 간선에 대해 가중치가 가장 작은 것들을 우선으로하여 MST의 조건을 만족할 수 있는 간선을 V-1개 선택하는 방법이다.

아직 선택되지 않은 간선들 중에 가중치가 가장 작으면서 사이클을 만들지 않는 간선을 탐욕적으로 선택하도록 구현한다.

Disjoint set(Union&Find) 으로 모든 간선에 대해 연결된 두 정점을 Union 해주면 사이클이 생성되는 경우 두 정점의 Find 연산 리턴 값이 같아지게 된다. 이를 이용해 간선을 선택했을 때 사이클이 생성되는지를 확인하고, 사이클이 생성되는 경우는 무시하도록 구현한다.

 우선순위 큐 자료구조를 사용하면 우선순위 큐에 저장된 모든 간선을 확인해야 하므로 O(E)가 되고, 간선을 확인하기 위해 pop연산을 수행해야 하므로 O(logE)가 된다. 따라서, 전체적으로 시간 복잡도는 O(ElogE)가 된다.

정점의 개수에 비해 간선의 개수가 적은 경우 유리한 알고리즘이다.