블로그 이사 중입니다 >> gumgood.github.io

Minimum Spanning Tree 본문

Problem Solving/분류없음

Minimum Spanning Tree

gumgood 2017. 5. 27. 03:53

무방향성 가중치 그래프 G에 대해

- Spanning tree : 그래프 G의 모든 node를 포함하는 Tree를 말한다. 그래프 G의 부분그래프

- MST(Minimum Spanning Tree) : G에 대한 spanning tree 중 가중치의 합이 가장 작은 tree


MST를 찾는 Greedy method가 있다. (Prim, Kruskal, Sollin...)

대표적인 Kruskal's algorithm에 대해서만 서술한다.


1. Kruskal's algorithm 수행과정

  ① graph의 모든 edge를 가중치의 오름차순으로 정렬한다.

  ② edge의 가중치가 작은 순으로 spanning tree에 추가해나간다.

  ③ 추가했을 때 spanning tree와 cycle이 생기는 간선은 제외한다.

  ④ ②~③을 모든 간선에 대해 반복한다.


2. Kruskal's algorithm 구현

  edge는 (cost, vertex1, vertex2)로 정의하여 오름차순으로 sort한다.

  spanning tree에 edge를 추가했을 때, cycle 생성여부를 쉽게 알 수 있을까? Disjoint set


  C++11


3. Kruskal's algorithm 시간복잡도

  edge들을 정렬하는데 O(ElogE)이고,

  Disjoint set은 O(1)이고, tree를 만드는데 O(E)이다.

  E는 최대 개이므로 전체 시간복잡도는 이다.


4. Kruskal's algorithm 증명

  Greedy method와 같이 증명 (참고)


5. Prim's algorithm 구현

  다익스트라와 비슷한(?) 느낌이다.


  C++11


'Problem Solving > 분류없음' 카테고리의 다른 글

Binary search algorithm - detail  (2) 2019.04.04
Fenwick Tree, BIT  (0) 2017.05.27
Minimum Spanning Tree  (0) 2017.05.27
Longest Increasing Subsequence  (0) 2017.05.27
Segment Tree (구간 트리)  (0) 2017.05.27
Disjoint-set  (0) 2017.05.27
Tag
0 Comments
댓글쓰기 폼