기본 개념
크루스칼과 프림 알고리즘은 모두 최소 신장 트리(MST)를 찾는 알고리즘이다.
최소 신장 트리 = 그래프의 모든 정점을 포함하는 트리, 모든 간선의 가중치 합이 최소인 트리
동작 원리
프림 알고리즘
프림 알고리즘은 시작 정점에서 시작하여 인접한 정점 중 가중치가 가장 작은 정점을 선택하여 MST를 찾는 알고리즘이다. 선택된 정점은 반드시 시작 정점과 연결된 정점이어야 한다.
크루스칼 알고리즘
크루스칼 알고리즘은 가중치가 작은 간선을 순서대로 선택하여 MST를 찾는 알고리즘이다. 따라서, 모든 간선들의 가중치를 오름차 순으로 정렬한 상태에서 그래프를 탐색하는 식으로 진행된다. 선택된 간선은 반드시 두 개의 서로 다른 서로소 집합을 연결해야 합니다. 쉽게 설명하자면, 선택된 간선이 반드시 두 개의 서로 다른 집합을 연결해야 선택된 간선이 MST에 포함될 수 있다.
크루스칼(Kruskal) vs 프림(Prim)
기록