최소 신장 트리(MST)


신장 트리 (Spanning Tree)

최소 신장 트리에 앞서 신장 트리란 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프이다.
신장트리의 조건은 다음과 같다.

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

최소 신장 트리 (Minimum Spanning Tree)

가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭한다.
최소 신장 트리의 특징은 다음과 같다.

  1. 간선의 가중치의 합이 최소여야 한다.
  2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
  3. 사이클이 포함되어서는 안된다.

최소 신장 트리 알고리즘 중 대표적인 알고리즘이 크루스칼 알고리즘과 프림 알고리즘이다

크루스칼 알고리즘 (Kruskal Algorithm)

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 스패닝 트리를 찾음으로써 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘이다.

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

프림 알고리즘 (Prim Algorithm)

시작 정점을 기준으로 가장 작은 간선과 연결된 정점을 선택하며 신장 트리를 확장 시키는 알고리즘으로 정점 선택을 기반으로 한다.

  1. 임의의 간선을 선택
  2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택
  3. 모든 정점이 선택될 때까지 반복

참고

https://velog.io/@dnjscksdn98/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC
https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html




© 2020.09. by 다로

Powered by theorydb