: 하나의 그래프가 있을 때 1) 모든 노드를 포함하면서 2) 사이클이 존재하지 않는 부분 그래프를 의미함.
: 최소 신장 트리 알고리즘. 즉, 모든 노드를 최소한의 비용으로 연결하기. Greedy 알고리즘의 일종이다.
[ before ]
[ after ]
[ 방법 ]
: 모든 간선에 대하여 정렬을 수행한 뒤 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 단, 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않는다.
구체적인 순서는 다음과 같다.