그리디 알고리즘 -(1) Minimum Spanning Trees

정의

일련의 선택을 함으로써 해결책에 도달

각 선택은 현재단계의 최적 9 -> 전체적으로 최적은 아님

 

 

구현 순서

1. Selection Procedure

기준에 따라 아이템을 선택해 집합에 추가하기

2. Feasibility Check

집합에 넣어도 되는지 안되는지 체크하기

3. Solution Check

완성된 집합이 solution이 맞는지 아닌지 결정하기

 

 

 Minimum Spanning Trees

* Acyclic Graph : cycle이 없는 그래프

*Tree: acycli, connected, undirected 한 그래프

(자료구조 트리와는 다름)

* Spanning Tree: 주어진 그래프의 모든 vertice를 포함하여 연결시킨 subgraph

* Minimum Spanning Tree: 최소의 weight를 갖는 spanning tree

-> cycle이 없고 주어진 그래프의 모든 vertice를 포함하여 최소의 weight를 갖도록

방향이 없이 연결된 그래프

 

 

해결 알고리즘 (1) Prim's Algorithm

1. edge를 담을 집합 F와 vertex를 담을 집합 Y 생성

2. 시작점을 골라서 집합 Y에 담기

3. Y에 들어있지 않은 vertex 중 방금 Y에 넣은 vertex와 가장 가까운 vertex 선택하기

4. Y에 선택한 vertex 넣고, F에 edge 넣기

5. edge를 n-1개 고를때까지 3,4 반복

--> vertice 선택 기반

 

<시간복잡도>

Basic operation: while루프안에 for루프 2개

Input size: n 

-> T(n) = 2* (n-1) * (n-1) = 세타 n^2 (배열을 썼을 경우)

* 배열 대신 힙을 쓰고 adjency matrix보다 adjency list를 쓴다면 

시간복잡도는 log n * edge 총 개수

 

 

<최적의 해인지 증명하기>

1. 빈 집합은 promising하다

2. edge가 담긴 집합 F가 promising 하다고 가정

3. F에 새롭게 골라진 minimum weight인  edge e를 담았을 때 promising 한가? 를 보이기

-> (1) e가 완성된 최적해 F'에 들어있는 경우: F도 당연 promising

    (2) e가 완성된 최적해 F'에 들어있지 않은 경우: 

F'에 e가 들어가면 cycle이 돼버려서 F'에 있지 않은 것. 

F'에서 cycle을 만드는 다른 edge e'을 제거하면 e가 F'에 들어갈 수 있게 됨.

e는 minimum weight이므로 F' + e - e'은 spanning tree가 됨.

따라서 e의 weight는 e'보다 작거나 같다. 사실상 같을 수밖에 없음. 

즉, promising 함으로 증명 끝.

 

 

해결 알고리즘 (2) Kruskal's Algorithm

1. 모든 edge들의 weight를 오름차순으로 정렬

2. 정렬된 edge 리스트에서 순서대로 사이클을 형성하지 않는 edge를 선택한다.

*사이클 생성 여부 확인? 

-> 추가하고자 하는 edge의 양끝 vertice가 현재 집합에 속해있는지 체크

* Disjoint Set?

-> 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 자료구조

3. 선택한 edge를 현재 집합에 추가해 나간다.

4. edge를 다 고를 때까지 2번, 3번 반복

--> edge 선택 기반

 

 

Disjoint Set 자료구조 사용

1. Initial(n) : n개의 disjoint subset을 초기화. 각 부분집합(disjoint subset)은 1과 n사이의 인덱스 중

하나를 정확히 포함

ex) {1} , {2}, {3},....., {n}

2. P=find(i) : i를 포함하는 집합을 가리키는 포인터 P

3. merge(p, q) : p와 q 두 집합을 병합하는 함수

4. equal(p, q) : p와 q가 같은 집합을 가리키고 있다면 true를 반환

 

 

<시간복잡도>

Basic operation: 비교 연산

Input Size: n(vertices의 개수), m(edges의 개수)

-> edge 정렬 시간: 세타 m lg m (using MergeSort)

  while 루프: 세타 m lg m( using DisjointSet)

n개의 disjoint sets 초기화: 세타 n

 

*edge의 개수 m은 n-1 ≤ m ≤ n(n-1)/2의 값을 가질 수 있다.

하나의 vertice랑만 연결되면 n-1개

모든 vertice와 연결되면 n(n-1)/2개

--> 따라서 worst case는 세타 n^2 lg n^2=n^2 lg n

 

 

<최적해인지 증명하기>

 

prim이 알고리즘과 비슷하게 증명 가능

 

 

Prim’s Algorithm vs. Kruskal’s Algorithm

1. 만약 edge의 개수가 n-1에 가깝다면 graph가 sparse(희박)하다고 함.

-> Kruskal's Algorithm이 더 좋음

2. 만약 edge의 개수가 n(n-1)/2에 가깝다면 graph가 dense(밀집)하다고 함

-> Prim's Algorithm이 더 좋음