1. greedy Algorithm
greedy 알고리즘은 선택을 반복하는 알고리즘들 중 비교적 간단하게 선택하고
선택한 것은 바꾸지 않는 알고리즘이다.
2. Minimum Spanning Tree (MST)
Spanning Tree는 그래프의 모든 정점과 간선의 부분집합으로 구성된 부분 그래프이다.
MST는 주어진 그래프의 연결 그래프들 중 엣지들의 비용이 최소가 되도록 하는 그래프이다. (단, 사이클을 생성X)
사이클이 있으면 안되는 이유는 사이클이 없어도 되기 때문이다.
사이클이 중 하나를 없애도 연결그래프는 유지가 된다. 게다가 비용까지 감소가 된다.
우리는 '최소'를 찾고 있으므로 사이클이 있을필요가 없다. 아니, 있으면 안된다.
3. Prim Algorithm
프림 알고리즘의 아이디어는 먼저 하나의 노드를 선택하고, 인접한 edge들 중에서 가장 작은 비용의 edge를 추가하며
경로를 만드는 것이다. 단 사이클을 만들지 않아야한다.
이 것을 spannig tree가 될 때까지 반복하면 된다. (edge는 n-1개 node는 n개 가 되어야한다.)
위 그림으로 예시를 들어보자면,
먼저 1을 시작노드로 설정하겠다.
1노드는 6노드와 2노드와 인접해있다. 이 중 저렴한 노드인 6을 선택한다.
다음으로 고려할 것은 6에서 5 가는 엣지랑 1에서 2 가는 엣지이다.
둘 중에 6에서 5가는 엣지가 더 저렴하므로 선택된다.
5→4 5→7 1→2 중에 선택해야하는데 가장 저렴한건 5→4이다.
이런식으로 사이클이 생기지만 않게 작은 weight만 찾아가면 된다.
결과는 1→6→5→4→3→2→7 이 될 것이다.
증명 (proof by induction)
증명하기 전에 몇가지 가정을 이해해야한다.
- Tmst는 많은 정답 Edge set 중 하나 이다.
- T는 prim이 만들어가고 있는 Edge set이다. 알고리즘이 끝나면 Tmst가된다.
T⊆Tmst 를 유지한다는 것을 보이자.
Base : 알고리즘 시작 시 node 1개, edge 0개이므로 T=∅ 이다. 따라서, 가 항상 성립한다.
Step : T에 k개의 노드가 들어있을 때, T⊆Tmst라고 성립하자. 그 다음 순서를 진행하면 새로운 edge가 하나 추가될 것이다. 그 edge를 e 라고 하자. 다음 단계의 T를 T′라고 하면
- Case 1: 이면 명제 성립한다.
- Case 2: 이면 반드시 사이클이 생성된다. 이 경우 사이클 내부에 (e'≠e) ∧ (e' ∉ T′) ∧ (T∪{e'}is not a cycle) ∧ (e' is connected to T) 를 만족하는 edge 가 존재한다. 다시말해보자면, e랑 만나는 두개의 노드 중 T에 들어가는 노드를 a, 들어가지 않은 노드를 b 라고 하자. a에서 b로 들어가는 사이클을 돌다보면 한쪽 노드는 T에 인접하고 한쪽 노드는 인접하지 않는 노드가 있는데, 그 노드가 e'이다.
e'의 weight에 따라 또 3 case로 나뉜다.
- Case 2-1: 이면 알고리즘은 e'를 추가할 것이다.
- Case 2-2: 이면 인 더 좋은 답이 존재하게 되므로 T가 성립된다는 것이 모순
- Case 2-3: 이면 또 다른 정답!
4. 성능
정점 n개, 엣지 m개
- Graph 표현: Linked List 로 구현 -
- 노드가 트리에 들어갔는지 마킹(전부 들어가야 끝나니까) : 노드 길이만큼 일반 배열 생성해서 구현. boolean 값으로 몇번 노드가 있는지 없는지만 확인하는 용도이다. - (edge 하나 꺼낼때마다 2칸씩 확인하므로 총 )
- Edge 저장소: Priority Queue로 구현 - 모든 edge들이 2번씩 넣고 빠지고)
→ 시간복잡도:
'학부 내용 정리 > [ 2-2 ] 알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] 최단거리 : Dijkstra Algorithm (0) | 2022.10.12 |
|---|---|
| [ 알고리즘 ] MST(2) : Kruskal Algorithm (0) | 2022.10.11 |
| [ 알고리즘 ] 자료구조 내용 복습 (0) | 2022.10.09 |
| [ 알고리즘 ] 정렬(3) : Quick Sort (0) | 2022.10.09 |
| [ 알고리즘 ] 정렬(2) Merge, Recursive Merge Sort (0) | 2022.10.09 |