[자료구조] 최소 신장 트리 Minimum Spanning Tree

Spanning Tree (신장 트리)

• Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임)

• 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프

• 신장 트리의 조건

  • 본래의 그래프의 모든 노드를 포함해야 함
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족시킴 (사이클이 존재하지 않음)
  

• DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다.

• 탐색 도중에 사용된 간선만 모으면 만들 수 있다.

• 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.

• Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.

• 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다.

최소 신장 트리

• Minimum Spanning Tree, MST 라고 불리움
• 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함

특징

• 간선의 가중치의 합이 최소여야 한다.
• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
• 사이클이 포함되어서는 안된다.
• 가중치 무방향 그래프
• Kruskal, Prim algorithm 을 사용하여 구현 가능하다.