최소 비용 신장 트리

신장 트리

→ 신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리이다.

• 모든 정점들이 연결되어 있어야 하고, 사이클을 포함해서는 안된다.
  • 따라서, 그래프에 있는 n 개의 정점을 정확히 (n-1) 개의 간선으로 연결하게 된다.

• 신장 트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다.
  • 신장 트리는 그래프의 최소 연결 부분 그래프가 된다.

최소 비용 신장 트리

최소 비용 신장 트리(MST: minimum spanning tree)

→ 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 트리

• 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다.
  • 간선의 가중치의 합이 최소이어야 한다.
  • 반드시 (n-1) 개의 간선을 사용해야 한다.
  • 사이클이 포함되서는 안 된다.

Kruskal의 MST 알고리즘

→ Kruskal의 알고리즘은 탐욕적인 방법(greedy method)를 사용한다.