MST – Kruskal 알고리즘 (추상적)

Presentation on theme: "MST – Kruskal 알고리즘 (추상적)"— Presentation transcript:

1 MST – Kruskal 알고리즘 (추상적)
1. F := 0; 2. 서로소(disjoint)가 되는 V 의 부분집합 들을 만드는데, 각 부분집합 마다 하나의 정점만 가지도록 한다. 3. E안에 있는 이음선을 가중치의 비내림차순으로 정렬한다. 4. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복하라 (a) 선정 절차: 최소의 가중치를 가진 이음선을 선정한다. (b) 적정성 점검: 선정된 이음선이 두 개의 서로소인 부분 집합에 속한 정점을 잇는다면, 그 두 집합을 하나의 집합으로 합치고, 그 이음선을 F에 추가한다. (c) 해답 점검: 만약 모든 부분집합이 하나의 집합으로 합치 어지면, 그 때 T = (V,F)가 최소비용 신장 트리 이다.

2 MST – Kruskal 알고리즘 (추상적)

3 MST – Kruskal 알고리즘 (구체적)
주어진 그래프에 대한 “서로소 집합 추상 데이터 타입” (disjoint set - abstract data type) index i; // node vi set_pointer p, q; initial(n): n개의 서로소 부분집합을 초기화 (하나의 부분집합에 1에서 n사이의 정점 인덱스가 정확히 하나 포함됨) p = find(i): 정점 인덱스 i가 포함된 집합 p를 넘겨줌 merge(p, q): 두 개의 집합을 가리키는 p와 q를 합병 equal(p, q): p와 q가 같은 집합을 가리키면 true를 넘겨줌

4 MST – Kruskal 알고리즘 (구체적)
[복습] Data Abstraction (in Computer Science) Separation of a data type’s logical properties from its implementation Abstract Data Type (ADT) a specification of a set of data and a set of operations that can be performed on the data Data and operations are specified independently of any particular implementation. LOGICAL PROPERTIES IMPLEMENTATION What are the possible values? How can this be done in C++? What operations will be needed? How can data types be used?

5 MST – Kruskal 알고리즘 (구체적)
set_of_edges kruskal(int n, int m,//입력:정점의 수 n,이음선의 수 m set_of_edges E){//가중치를 포함한 이음선의 집합 E index i, j; set_pointer p, q; edge e; set_of_edges F; E에 속한 m개의 이음선을 가중치의 비내림차순으로 정렬; F = emptyset; initial(n); while (F에 속한 이음선의 개수가 n-1보다 작다) { e = 아직 점검하지 않은 최소의 가중치를 가진 이음선; i, j = e를 이루는 양쪽 정점의 인덱스; p = find(i); q = find(j); if (!equal(p, q)) { merge(p, q); F에 e를 추가; } return F; equal(p, q) = true는 e를 추가할 경우 cycle이 형성됨을 의미한다.

6 MST – Kruskal 알고리즘의 분석 단위연산: find 등에서 수행되는 (비교) 명령문
입력크기: 정점의 수 n과 이음선의 수 m 최악의 경우 분석 1. 이음선 들을 정렬하는데 걸리는 시간: W(n)  (m lg m)  정렬의 이론적 하한 3. n개의 서로소 집합(disjoint set)을 초기화하는데 걸리는 시간: (n) 2. 반복문 안에서 걸리는 시간: 최악의 경우 루프를 m번 수행. - 최소의 가중치를 가진 이음선 구하기: (1)에 수행 - 부록 C의 서로소 집합 자료구조(disjoint set data structure)를 사용하 여 구현하면, find, equal, merge는 (lg m)에 수행된다. - 따라서, m번 반복에 대한 시간복잡도는 (m lg m)이다.

7 MST – Kruskal 알고리즘의 분석 분석 (계속)
그런데 여기서 m  n - 1이고, 위 분석에서 1과 3은 2를 지배하게 되므로, W(m, n) = (m lg m)가 된다. 그러나, 최악의 경우에는, 모든 정점이 다른 모든 정점과 연결이 될 수 있기 때문에(fully connected), 가 된다. 그러므로, 최악의 경우의 시간복잡도는 다음과 같다.

8 MST – Kruskal 알고리즘의 최적 여부 검증
보조정리 4.2: G = (V,E)는 가중치 포함 비방향성 연결 그래프라고 하자. E의 부분집합인 F는 유망하며, e는 F  {e}하여 순환이 생기지 않는 E – F 에 속한 최소가중치 이음선이라고 하자. 그러면, F  {e}는 유망하다. (즉, Kruskal의 방법을 사용한 F  {e}는 유망하다.) 정리 4.2: Kruskal 알고리즘은 항상 MST를 만들어 낸다.

9 MST – Prim vs. Kruskal 분석 결과 비교
(Kruskal) 연결된 그래프에서 이음선 개수 m은 다음 범위를 갖는다. 그래프가 sparse하면, m  n이므로, (n lg n)이 된다. 반면에 dense이면, m  n2이므로, (n2 lg n)이 된다.

10 MST – More Improved Algorithms
알고리즘의 시간복잡도는 그 알고리즘을 구현하는데 사용하는 자료구조에 좌우되는 경우도 있다. Heap을 사용하여 개선된 Prim 알고리즘의 시간 복잡도

11 단일 출발점 최단경로 문제 (Single Source Shortest Path Problem)
제3장에서 모든 정점을 대상으로 하는 최단 경로를 구하는 (n3)의 DP 알고리즘 (Floyd 알고리즘)을 개발하였다. 어떤 특정한 정점에서 다른 모든 정점까지 최단경로만 필요한 경우에는 이 알고리즘은 너무 비용이 크다. 본 장에서는, 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단경로 구하는 문제를 다룬다. Dynamic Programming방식의 Floyd 알고리즘에서의 재귀관계식 Greedy 방법을 활용한 Dijkstra의 단일출발점 최단경로 알고리즘은 Θ(n2)이다.

12 Dijkstra 알고리즘 (추상적) 1. F := 0; 2. Y := {v1}; // 단일 소스: v1
3. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복하라 (a) 선정 절차/적정성 점검: v1에서 Y에 속한 정점 만을 거쳐서 최단경로가 되는 정점인 v를 V - Y에 속한 정점 중에서 선정한다 (b) 그 정점 v를 Y에 추가한다. (아래 그림에서 vi) (c) v로 이어지는 최단경로 상의 이음선을 F에 추가한다. (d) 해답 점검: Y = V가 되면, T = (V,F)가 최단경로를 나타내는 그래프 이다.

13 Dijkstra 알고리즘 (추상적) – 예1 Y := {v1} F := {} Y := {v1, v5}
F := {(v1, v5)} Y := {v1, v5, v4} F := {(v1, v5), (v5, v4)} MST 문제의 Prom 알고리즘과 유사 하지만, Dijkstra 알고리즘은 “출발점에서의 거리”를 고려해야 한다. Y := {v1, v5, v4, v3} F := {(v1, v5), (v5, v4), (v1, v3)} Y := {v1, v5, v4, v3, v2} F := {(v1, v5), (v5, v4), (v1, v3), (v4, v2)}

14 Dijkstra 알고리즘 (추상적) – 예2 Y := {v1} F := {} Y := {v1, v2}
F := {(v1, v2)} Y := {v1, v2, v3} F := {(v1, v2), (v1, v3)} Y := {v1, v2, v3, v5} F := {(v1, v2), (v1, v3), (v3, v5)} Y := {v1, v2, v3, v5, v4} F := {(v1, v2), (v1, v3), (v3, v5), (v3, v4)}

15 Dijkstra 알고리즘 (추상적) – 예3 1 2 4 5 6 3 3 1 2 4 5 6 1 2 4 5 6 3 1 2 4 5 6 3 1 2 4 5 6 3 1 2 4 5 6 3

16 Dijkstra 알고리즘 (구체적) – 1/3 가중치 그래프 W는 Prim 알고리즘과 같이 이차원 배열로 표현
Prim 알고리즘의 nearest[], distance[] 대신에 touch[], length[] 사용 touch[i]: Y에 속한 노드들만을 거쳐서 v1에서 vi로 가는 현재 최단경로 상의 마지막 이음선을 <vx, vi>라 할 때, Y에 속한 노드 vx의 인덱스인 x length[i]: Y에 속한 노드들만을 거쳐서 v1에서 vi로 가는 현재 최단경로의 길이 vx 25 vj 10 노드 vi가 Y에 포함된 상태에서는 touch[j] = i, length[j] = 25 (= ) touch[k] = y, length[k] = 28 (=8+20) 2 Set Y 3 10 v1 vi va 8 vy 20 vk 노드 vi가 포함되기 전 상태에서는 touch[i] = a, length[i] = 15 (=2+3+10) touch[j] = x, length[j] = 27 (=2+25) touch[k] = y, length[k] = 28 (=8+20)

17 Dijkstra 알고리즘 (구체적) – 2/3 Dijkstra 알고리즘
set_of_edges dijkstra(int n, number[][] W) { index i, vnear; number min; set_of_edges F; index[] touch = new index[2..n]; number[] length = new number[2..n]; F = empty_set; for(i=2; i <= n; i++) { // 초기화 touch[i] = 1; // 초기에는 Y에 노드가 v1밖에 없음 length[i] = W[1][i]; // (v1,vi)의 가중치로 초기화 } // see the next page

18 Dijkstra 알고리즘 (구체적) – 3/3 알고리즘 (계속)
노드 하나를 Y에 넣기 위해, Y에서 도달 길이가 가장 짧은 vvnear를 선택한다. 알고리즘 (계속) repeat(n-1 times) { // n-1개의 정점을 Y에 차례로 추가한다 min = infinite; for(i=2; i <= n; i++) { if (0 <= length[i] < min) { // length[i]를 검사하여 min = length[i]; // Y에 가장 가까이 있는 노드 vnear = i; // vnear를 찾는다. } e = touch[vnear]가 인덱스인 정점에서 vnear가 인덱스인 정점을 잇는 이음선; F에 e를 추가; for(i=2; i <= n; i++) if (length[vnear] + W[vnear][i] < length[i]) { length[i] = length[vnear]+W[vnear][i]; // Y에 속하지 않는 touch[i] = vnear; // 조건에 맞는 노드에 대해 length[i]를 갱신한다. length[vnear] = -1; // vnear가 인덱스인 노드를 Y에 추가한다. } // end of repeat return F; } // end of main 이 부분이 Prim 알고리즘과 상이 노드 vnear의 추가에 따라, 도달 거리를 갱신한다.

19 Dijkstra 알고리즘 (구체적) Dijkstra 알고리즘의 동작과정 7 7 5 vnear=2 vnear=3 vnear=5
touch length 7 7 5 vnear=2 vnear=3 vnear=5

20 Dijkstra 알고리즘 (구체적) Dijkstra 알고리즘의 동작과정 7 vnear=4

21 Dijkstra 알고리즘의 분석 분석: T(n)  (n2)  repeat x 2-for-loop
힙(heap)으로 구현하면 (m lg n)임 최적여부의 검증(Optimality Proof) Prim의 알고리즘과 비슷하게 증명할 수 있다.