[Algorithms] Minimum spanning tree 알고리즘

우선 Spanning tree의 정의에 대해서 되돌아볼 필요가 있다.
스패닝 트리는 어떠한 그래프의 서브그래프이면서 그래프의 모든 버텍스를 포함하는 트리이다.
그러한 그래프가 edge에 weight를 가질때, weight의 합을 최소화하는 스패닝 트리를
Minimum spanning tree라 하며 그것을 구하는 알고리즘으로 Prim's algorithm과 Kruskal's algorithm이 있다.

위 두가지 방법은 Greedy Approach를 이용하여서 각자의 기준을 가지고 스패닝 트리를 만들게 된다.

우선 첫째로, Prim의 알고리즘은
하나의 버텍스에서 시작하여 인접한 버텍스 중 가장  웨이트가 작은 엣지로 연결된 버텍스를 선택하고 연결한다.
여기에서 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연결된 버택스를 선택한다는 것이 Greedy Criteria가 되서 연속적으로 만들어나가게 된다.
Greedy Approach의 특성상 이 방식으로 최적해, 즉 미니멈 스패닝 트리를 얻을 수 있다고 확신할 수 없지만, 여기에는 실제로 얻을 수가 있고 수학적 귀납법을 통해 증명할 수 있다.

리뷰할때 증명부분 살펴보자.

그리고 Kruskal의 알고리즘은
Set이론을 응용하여 모든 버텍스에 대해서 Disjoint subset으로 만든다.
그리고 엣지를 오름차순으로 정렬한 후 엣지의 웨이트가 작은 순서대로 엣지를 꺼내어 그 엣지로 연결되는 두개의 버텍스가 다른 set이라면 merge하며, 같은 set이라면 엣지를 버리는 방식으로 진행해 나가며 스패닝 트리를 만든다.
여기에서는 집합의 union과 find를 이용하여 알고리즘을 구현한다.
union은 두개의 집합을 합치는 것이며 find는 해당 버텍스가 들어있는 집합을 찾는 함수이다.
이또한 수학적 귀납법을 통해 최적해를 얻음을 증명할 수 있다.

두 알고리즘의 complexity는 Prim이 버텍스의 개수가 n일때 n^2 order, Kruskal이 엣지의 개수가 m일때 mlgm의 order를 가진다.
엣지의 개수는 n-1≤m≤n(n-1)/2 만큼 가능하므로 그래프의 edge가 sparse 한지 dense한지에 따라 복잡도가 달라진다.
그래프가 sparse하면 크루스칼의 알고리즘을, dense하면 prim의 알고리즘을 사용하는것이 효율적일 것이다.