최소 신장 트리 알고리즘(프림 알고리즘)

최소 신장 트리 알고리즘

---

그래프는 복잡한 작업 과정이나 구조를 표현하기 위해 사용되며, 자료구조의 일종입니다.

그래프 중 ‘루트’라는 정점에서 시작해 계층적으로 존재하는 모든 정점들이 1개 이상의 간선으로 연결된 그래프를 ‘트리’라고 합니다.

그래프가 어떻게 구성되어있는지에 따라서 유도될 수 있는 트리는 다양한데, 이런 다양한 트리를 ‘신장 트리’라고 합니다.

 이때 각 간선마다 가중치가 부여된다고 가정할 때 가중치의 합이 최소가 되는 트리를 유도할 수 있습니다. 이를 ‘최소 신장 트리’라고 합니다.

최소 신장 트리를 유도하기 위한 방법에는 프림 알고리즘, 크루스칼 알고리즘, 솔린 알고리즘이 있습니다.

---

프림 알고리즘

1. 임의의 정점을 선택 (현재 트리에 1개의 정점이 포함됨)

2. 해당 정점과 연결된 간선 중 가중치가 최소인 것을 선택 (트리에 2개의 정점이 포함됨)

※(만약 찾은 간선이 이미 트리에 있는 노드를 연결하는 경우 해당 간선은 선택하지 않음)※

※(만약 찾은 간선으로 인해 사이클(순환 관계)가 형성된다면 해당 간선은 선택하지 않음)※

3.모든 노드가 트리에 포함될 때까지 반복함 

예시:

1.A를 최초 출발 노드라고 가정한다면 A에 연결된 간선 중 가중치가 가장 작은 4를 선택(4 <6) [트리에 A, C 포함됨]

2.C에 연결된 간선 중 가중치가 가장 작은 3을 선택(3<4,7) [ 트리에 A, C, B포함]

3.B에 연결된 간선 중 가중치가 가장 작은 것은 3이지만 이미 C가 트리에 포함되어있으므로 선택하지 않음 & 3을 제외하면 가장 작은 것은 6으로 A, E를 연결하는 간선이다. 여기서 A를 연결하는 간선을 선택할 경우 ACB이 사이클을 형성하므로 A를 연결하는 간선은 선택할 수 없다. 따라서 E를 연결하는 간선을 선택한다.( 3 불가, 6 <7, A와 연결된 간선 불가[사이클 형성]) [트리에 A, C, B, E 포함]

4.E에 연결된 간선 중 가중치가 가장 작은 것은 6이지만 이미 B가 트리에 포함되어 있으므로 선택할 수 없다. 따라서 D와 연결된 10을 선택 [트리에 A, C, B, E, D포함]

5. 모든 노드가 트리에 포함되었으므로 종료

빨-주-노-초-파 순서

프림 알고리즘으로 구한 최소 신장 트리는 A-4-C-3-B-6-E-10-D입니다.

---