[알고리즘] 최소 신장 트리

신장트리

• Spanning Tree 라고 불린다.
• original 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프
• 신장트리의 조건
  1. 본래의 그래프의 모든 노드를 포함해야 한다.
  2. 모든 노드가 연결되어있어야 하지만
  3. 사이클이 존재하지 않아야 한다 ( 트리 이므로 )

 

최소 신장트리

• MST 라고 불린다.
• 가능한 신장트리 중에서 간선의 가중치 합이 최소인 신장트리

 

최소 신장트리를 찾는 알고리즘 2개

 

• 크루스칼 알고리즘 
• 프림 알고리즘

크루스칼 알고리즘

1. 모든 간선들의 가중치를 오름차 순으로 정렬
2. 가중치가 가장 작은 간선을 선택
3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다. ( 이때 사이클이 만들어지면 안된다 !)
4. 이 과정을 반복

 

프림 알고리즘

1. 임의의 간선을 선택한다.

2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택한다. ( 이때 이미 선택된 정점은 선택하지 않는다 )

3. 모든 정점이 선택될 때까지 반복한다.