정의는 정점의 집합 V와 가중치를 갖는 간선의 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오 다시 쉽게 말하면 최소 비용으로 모두를 잇는 방법이라고 볼 수 있다. 아래 그림을 보자 어떤 알고리즘에 의해 만들어졌을까? **이 아이디어는 Kruskal's Algorithm이라고도 부른다. 매 반복마다 최소 값을 꺼내기 때문에 Greedy라고도 부른다. 1. 그래프의 주어진 모든 간선을 최소힙(Min Heap) H 에 추가한다. 2. H로부터 간선, e을 하나 꺼낸다. 3. 해당 간선의 양 끝점이 T에 있는 경우 e 때문에 cycle이 발생할 수 있으니 e를 버리고 다시 2 단계로 돌아간다. 4. 해당 간선을 T, 트리에 추가시키고 ..
