신장트리는 비중있는 그래프 상에서 정점과 정점 사이에 경로를 단일화한 트리를 말합니다. 그리고 최소신장트리는 정점과 정점 사이의 경로의 합이 최소인 신장트리를 말합니다.
그래프에서 최소신장트리를 만드는 여러가지 방법 중에 가장 많이 알려진 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 추가하면서 트리를 확장하는 방법이고 크루스칼 알고리즘은 간선을 추가하면서 최소신장트리를 만드는 방법입니다.
먼저 프림 알고리즘을 살펴봅시다.
프림 알고리즘(graph:원본 그래프)
하나의 정점을 선택한다.
반복(선택한 정점 개수가 graph의 정점 개수보다 작다면)
선택한 정점에서 갈 수 있는 모든 정점 중에 최소 비중의 간선으로 이어지는 정점을 선택
*정점을 선택할 때 이미 선택한 정점은 선택할 없음*
[그림 7.1] 원본 그래프에서 프림 알고리즘으로 최소신장트리를 만드는 예를 들어볼게요.
그래프의 정점을 하나 선택합니다. 처음 선택하는 정점은 무엇을 선택해도 관계가 없습니다. 여기서는 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)합니다. 이와 같은 원리로 모든 정점을 선택할 때까지 반복합니다.
[그림 7.2]는 [그림 7.1] 원본 그래프를 프림 알고리즘으로 최소신장트리를 만드는 과정을 도식한 것입니다.
