신장트리는 비중있는 그래프 상에서 정점과 정점 사이에 경로를 단일화한 트리를 말합니다. 그리고 최소신장트리는 정점과 정점 사이의 경로의 합이 최소인 신장트리를 말합니다.
그래프에서 최소신장트리를 만드는 여러가지 방법 중에 가장 많이 알려진 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있어요. 프림 알고리즘은 정점을 추가하면서 트리를 확장하는 방법이고 크루스칼 알고리즘은 간선을 추가하면서 최소신장트리를 만드는 방법이예요.
먼저 프림 알고리즘을 살펴볼게요.
프림 알고리즘(graph:원본 그래프)
하나의 정점을 선택한다.
반복(선택한 정점 개수가 graph의 정점 개수보다 작다면)
선택한 정점에서 갈 수 있는 모든 정점 중에 최소 비중의 간선으로 이어지는 정점을 선택
*정점을 선택할 때 이미 선택한 정점은 선택할 없음*
위 그래프에서 프림 알고리즘으로 최소신장트리를 만드는 예를 들어볼게요.
프림 알고리즘은 최소 비용의 정점을 그래프의 정점 개수만큼 선택하는 알고리즘입니다. 단 선택하는 정점은 이미 선택한 정점과 이웃이어야 하고 사이클이 발생하지 말아야 합니다.
최초 선택하는 정점은 무엇이든 선택할 수 있습니다. 여기서는 A를 선택할게요.
그리고 A와 인접한 정점 중에 비중이 제일 작은 간선으로 이어진 정점을 선택합니다. 정점 A와 이어진 정점은 B, D, E가 있는데 최소 비중으로 이어진 정점은 D이므로 D를 선택(A,D)합니다. 이제 선택한 정점 A와 D와 인접한 정점 중에 비중이 제일 작은 간선으로 이어진 정점을 선택합니다. B, C, E, F, H 정점이 인접한 정점이며 최소 비중으로 이어진 정점 B를 선택(A, D, B)를 선택합니다. 다시 정점 A, D, B와 인접한 정점 중에 비중이 제일 작은 간선으로 이어진 정점을 선택합니다. C, E, F, H 정점이 인접한 정점이며 최소 비중으로 이어진 정점 H를 선택(A, D, B, H)합니다. 정점 A, D, B, H와 인접한 정정 중에 비중이 제일 작은 간선으로 이어진 정점을 선택합니다. C, E, F, G 정점이 인접한 정점입니다. 최소 비중으로 이어진 정점 C를 선택(A, D, B, H, C)합니다.
이와 같은 원리로 모든 정점을 선택할 때까지 반복합니다.
아래 그림은 프림 알고리즘으로 최소신장트리를 만드는 과정을 도식한 것입니다.