최소 신장 트리 : Kruskal(크루스칼) 알고리즘과 Prim(프림) 알고리즘

앞서 자료구조에서 그래프에 대한 기본적인 개념과 최소 신장 트리에 대해서 공부를 했습니다.

이번에는 최소 신장 트리를 구현할 수 있는 대표적인 두 가지 방법에 대해서 알아보겠습니다.

신장 트리는 모든 노드가 간선으로 연결되어 있어야 하지만, 사이클이 존재하면 안됩니다.

그리고 최소 신장 트리는 연결된 간선들의 가중치의 합이 최소가 되는 신장 트리입니다.

크루스칼 알고리즘과 프림 알고리즘 모두 최종적으로 연결된 간선의 수는 (노드의 개수-1) 개입니다.

 

 

 

1. Kruskal(크루스칼) 알고리즘

크루스칼 알고리즘은 그래프의 모든 간선을 가중치 순으로 정렬한 다음, 낮은 가중치를 가지는 간선을 차례대로 선택하여 신장 트리를 완성해나가는 방법

 

간선을 가중치 순으로 정렬하는 방법에는 선택 정렬, 버블 정렬, 삽입 정렬 등 여러 가지가 있습니다.

 

제가 구현한 크루스칼 알고리즘에서 사용한 자료는 노드가 100개이고 간선이 10000개인 [10000][3]의 행렬인데,

이때 [i][0]에는 시작노드, [i][1]에는 도착노드, [i][2]에는 간선의 가중치가 들어있습니다. 

버블정렬

버블정렬은 데이터의 개수가 n이라면 첫번째 시행에서 n번 비교하여 가장 큰 데이터를 맨 뒤로 정렬하고

다시 두 번째 시행에서는 n-1번 비교하여 두번째로 큰 데이터를 뒤로 정렬하는 방법이므로

전체 시행 횟수는 n번이고 각각의 시행마다 비교해야할 데이터의 개수는 1개씩 감소합니다.

 

 

 

 

 

2. Prim(프림) 알고리즘

프림 알고리즘은 트리를 확장시켜 최소 비용 신장 트리를 만드는 방법

크루스칼 알고리즘은 일단 노드를 모두 추가한 다음 알고리즘이 시작되었던 것과 비교하여, 프림 알고리즘은 임의의 시작 노드 1개만을 추가하여 알고리즘이 시작된다. 또한, 크루스칼 알고리즘이 남아 있는 간선 중에서 최소 비용을 가지는 간선을 선택했던 것과 비교하여, 프림 알고리즘은 현재 신장 트리와 연결된 간선 중에서 가장 작은 가중치를 갖는 간선을 선택한다는 것이 다르다.

 

제가 구현한 프림 알고리즘에서 사용한 자료에는 노드가 100개인 [100][100]행렬이고, 행에는 시작노드(from), 열에는 도착노드(to), [i][i]에는 각각 시작노드에서 도착노드로 이어진 간선의 가중치가 들어있습니다.

 

간선의 가중치가 최소인지 확인하고, 이미 그려진 간선인지 확인합니다.

 

모든 

아직 그려지지않은 최소 가중치를 가진 간선임을 확인하면 mstSet[from] 값을 false에서 true로 변경해줍니다.

 

 

 

 

정리

크루스칼 알고리즘은 가중치가 작은 간선부터 그려진다.

프림 알고리즘은 노드와 연결된 간선 중 가중치가 작은 간선을 그려나간다.