이산수학 그래프4: 최소신장 트리(minimum spanning tree)
신장트리
- 그래프 G = {V, E} 에서 V의 모든 정점을 포함하면서 순환(cycle)이 존재하지 않는 부분 그래프(subgraph)를 신장 트리라고 한다
- 최소 신장 트리 ( Minimum Spanning Tree,MST)
- 가중 그래프에서 가중치의 합을 최소로 하는 신장 트리
- 알고리즘 종류: Prim, Kruskal
- 프림 알고리즘
- MST알고리즘 중 하나로 선택한 정점들에서 갈 수 있는 에지 중에서 가장 낮은 가중치를 가진 에지를 선택하여 아직 선택하지 못한 정점을 포함 하도록 하여 MST를 구하는 알고리즘
- 그리디 알고리즘이지만 최종적으로 최적의 해를 찾아줌
- 시간 복잡도
- O(V*logE)
- 크루스칼 알고리즘
- MST알고리즘 중 하나로 에지들을 오름차순으로 정렬하여 가장 작은 가중치부터 고르는 알고리즘
- 단, 사이클이 생기지 않게 하기 위하여 Union-Find알고리즘을 이용함
- 프림과 동일하게 그리디알고리즘이지만 최종적으로 최적의 해를 찾아줌
- 시간 복잡도
- O(E*logE)
주말은 쉬어요