크루스칼 알고리즘
크루스칼 알고리즘이란
크루스칼 알고리즘과 프림 알고리즘은 최소 스패닝 트리를 만들기 위해 자주 쓰이는 알고리즘이다. 크루스칼 알고리즘의 원리는 매우 간단하다. 그래프의 간선들을 가중치 순으로 정렬해 가장 작은 가중치부터 그리디 알고리즘과 같이 선택해 트리에 포함시키는 것이다. 이 때 사이클이 생기면 안되므로 만약 간선이 추가됨으로서 연결 되는 정점이 같은 컴포넌트에 있는 경우 선택하지 않는다.
크루스칼 알고리즘의 구현
크루스칼 알고리즘의 핵심적인 부분은 같은 컴포넌트에 있는 정점들이 연결될 경우 선택하지 않는다는 점인데, 이를 위해 상호 배타적 집합을 사용한다. 상호 배타적 집합을 활용하면 두 정점이 같은 집합에 속하는지를 확인할 수 있고 두 정점을 같은 집합으로 합칠 수도 있다.
크루스칼 알고리즘의 시간 복잡도는 상호 배타적 집합의 연산에는 상수 시간이 걸리고 트리를 만드는데는 E의 시간복잡도를 필요로 하므로, 정렬하는데 드는 ElogE의 시간 복잡도를 갖는다.
프림 알고리즘
프림 알고리즘이란
프림 알고리즘 역시 기본적인 원리는 크루스칼 알고리즘과 유사하다. 크루스칼 알고리즘이 모든 간선들 중 가중치가 가장 낮은 간선을 선택했던 것과 달리 프림 알고리즘은 현재 트리에 포함된 정점과 포함되지 않는 정점을 이어주는 간선들 중 가중치가 가장 낮은 간선을 선택한다.
프림 알고리즘의 구현
프림 알고리즘을 구현하기 위해서는 가중치가 가장 낮은 간선을 찾는 과정이 필요한데, 이를 위해서 모든 간선을 다 돌아보는 것은 비효율적이다. 따라서 새로 정점이 추가될 때마다 트리에 포함되지 않으면서 그 정점과 연결된 정점의 가장 낮은 가중치를 갖는 간선을 매번 갱신해 주는 것이 좋다. 이렇게 하면 각 정점들은 트리와 연결된 가장 낮은 가중치를 갖는 간선을 항상 가지고 있기 때문에 모든 간선을 돌아볼 필요 없이, 트리와 연결될 수 있는 정점들만 확인하면 된다.
