알고리즘 : 최소 신장 트리1

신장 트리는?

• Spanning Tree 또는 신장 트리라고 함
• 원래 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프
• 신장트리의 조건
   - 본래의 그래프에서 모든 노드를 포함해야 함
   - 모든 노드가 서로 연결
   - 트리의 속성을 만족시킴

 

최소 신장 트리

• Minimum Spanning Tree(MST)
• 가능한 Spanning Tree중에서 간선의 가중치 합이 최소인 Spanning Tree를 말함

 

최소 신장 트리 알고리즘

• 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함
• 대표적인 최소 신장 트리 알고리즘
  - Kruskal's algorithm (크루스칼 알고리즘) Prim's algorithm (프림 알고리즘)

 

크루스칼 알고리즘(Kruskal's algotithm)

1. 모든 정점을 독립적인 집합으로 만든다.

2. 모든 간선을 비용을 기준으로 정렬하고 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.

3. 두 정점의 최상위 정점을 확인하고 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로

   사이클이 생기지 않도록 하는 것임)