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) Variables Set에 속한 각 원소들: 각 정점들의 인덱스 (ex. i, j) Operations 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 variables and a set of operations that can be performed on the data Variables and operations are specified independently of any particular implementation. LOGICAL PROPERTIES IMPLEMENTATION What are the possible variables? How can this be done in C++ or java? 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(m)  (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 알고리즘의 시간 복잡도