최소 신장트리 : 가중치가
있는 그래프 G에서 최소 가중치로
구성된 신장트리, Kruskal의
알고리즘과 Prim의 알고리즘
Prim의 알고리즘
: Dijkstra 알고리즘과
유사하나 Prim의 알고리즘은
루트에서 시작하지 않고
현재까지 완성된 트리의
각 노드에서 인접한 정점사이의
값이 가장 작은 정점을
트리로 흡수한다. 사이클
제외함.
Kruskal의 알고리즘
: 모든 간선들의 비용을
오름차순으로 정렬하고
비용이 적은 것부터 순차로
선택하되, 사이클이 발생하는
간선 제외
*
Prim 의 알고리즘이나 Kruskal의 알고리즘
모두 같은 결과를 가져온다. Prim의 알고리즘은
Dijkstra(다익스트라)의 알고리즘과
같이 한 노드에서 출발하여 최소신장 트리르
구하나, Kruskal 의 알고리즘은 모든 간선들의
비용을 오름 차순으로
정렬하여 작은 것부터 그려 나가므로 구하기
쉽다.