인하대 데이터구조 12주차 Homework 4 크루스칼 알고리즘

1. Problem definition

크루스칼 알고리즘은 그래프 이론에서 최소 신장 트리를 찾기 위해 개발된 효율적인 알고리즘이다. 이 알고리즘은 주어진 연결 그래프에서 모든 정점을 포함하면서 사이클이 없는 최소 가중치의 트리를 구성하기 위해 사용된다. 최소 신장 트리는 그래프의 모든 정점을 연결하되, 사용되는 간선의 가중치 합이 최솟값이 되는 특징을 지닌다. 이러한 최소 신장 트리는 네트워크 설계, 클러스터링, 그리고 다양한 최적화 문제에서 중요한 역할을 한다. 특히, 크루스칼 알고리즘은 엣지 중심의 접근 방식을 사용하여 먼저 간선들을 가중치에 따라 정렬하고, 그 후 연결 요소를 유지하며 간선을 추가해 나가는 방식으로 진행된다. 크루스칼 알고리즘의 핵심 문제는 비연결 그래프에서 최소 신장 트리를 구성하는 것이다. 비연결 그래프는 일부 정점들이 간선으로 연결되어 있지 않아서 여러 개의 연결된 구성 요소를 포함할 수 있다. 이 경우, 크루스칼 알고리즘은 먼저 모든 간선을 가중치에 따라 정렬한 후, 가장 가벼운 간선부터 시작하여 현재의 그래프에 포함시키고, 사이클이 발생하지 않도록 확인하는 과정을 반복한다. 이때 사이클의 존재 여부…