• 신장트리 : 그래프 G에 있는 모든 정점과 그 정점들을 연결하는 간선으로 구성된 트리
  • 최소 신장트리 : 가중치가 있는 그래프 G에서 최소 가중치로 구성된 신장트리, Kruskal의 알고리즘과 Prim의 알고리즘
    1. Prim의 알고리즘 : Dijkstra 알고리즘과 유사하나 Prim의 알고리즘은 루트에서 시작하지 않고 현재까지 완성된 트리의 각 노드에서 인접한 정점사이의 값이 가장 작은 정점을 트리로 흡수한다. 사이클 제외함.
    2. Kruskal의 알고리즘 : 모든 간선들의 비용을 오름차순으로 정렬하고 비용이 적은 것부터 순차로 선택하되, 사이클이 발생하는 간선 제외

 

    * Prim 의 알고리즘이나 Kruskal의 알고리즘 모두 같은 결과를 가져온다. Prim의 알고리즘은 Dijkstra(다익스트라)의
       알고리즘과 같이 한 노드에서 출발하여 최소신장 트리르 구하나, Kruskal 의 알고리즘은 모든 간선들의 비용을 오름
       차순으로 정렬하여 작은 것부터 그려 나가므로 구하기 쉽다.