[java] 최소 신장 트리 알고리즘
최소 신장 트리(Minimum Spanning Tree)는 그래프에서 모든 정점을 포함하는 트리 중에서 모든 간선의 가중치의 합이 최소인 트리를 말합니다. 이는 주어진 그래프에서 가장 중요한 연결을 나타내는 알고리즘입니다.
여러 가지 최소 신장 트리 알고리즘 중에서 대표적인 것은 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있습니다. 각각 다음과 같은 방식으로 동작합니다.
크루스칼(Kruskal) 알고리즘
- 그래프의 모든 간선들을 가중치의 오름차순으로 정렬한다.
- 가중치가 가장 작은 간선을 선택하고 사이클을 형성하지 않는지 확인한다.
- 사이클을 형성하지 않는다면 해당 간선을 선택한다.
- 사이클을 형성한다면 해당 간선을 건너뛴다.
- 모든 정점이 포함될 때까지 2단계를 반복한다.
프림(Prim) 알고리즘
- 임의의 시작 정점을 선택하고 이를 현재 신장 트리의 정점으로 지정한다.
- 현재 신장 트리와 인접한 정점들 중에서 가장 가까운 정점을 선택한다.
- 선택된 정점을 현재 신장 트리에 추가한다.
- 모든 정점이 포함될 때까지 2단계와 3단계를 반복한다.
이러한 알고리즘들을 사용하여 최소 신장 트리를 구할 수 있습니다. 이를 통해 그래프 내에서 중요한 관계를 찾고 최적의 연결을 실현할 수 있습니다.