공부/알고리즘2011. 7. 13. 16:01


Spanning tree
 

그래프에서 그래프의 모든 정점을 다 포함하는 트리.
부분 그래프이다. 트리라서 사이클이 없다.

Minimum spanning tree (MST)
 

spanning tree 중에서 가중치 합이 최소가 되는 spanning tree.
N개 vertex가 있으면 edge는 N-1개 있다.

일반적인 MST
처음에 A를 0으로 놓고 safe edge를 계속 추가해 나간다. 더 이상 안나올때까지 반복.
safe edge : 단계마다 하나의 edge를 선택할 때, minimum spanning tree를 유지하도록 하는 edge.
respect a set A : 그래프를 하나의 선으로 나눌 때, A의 어떤 edge도 그 선을 지나가지 않을 때, 그 선이 A를 respect한다고 한다.
light edge : respect하게 cut(나눈 선)을 지나는 edge 중에서 최소 weight를 가진 edge들 중 하나. (light edge가 여러개 일 수도 있다. 그리고 어떻게 cut을 하느냐에 따라 light edge가 달라질 수 있다.)

light edge면 safe edge이다.

MST 구하는 방법

1. Kruskal algorithm
set A는 forest이다.
전체 forest에서 두개의 tree를 연결하는 weight가 가장 작은 edge를 찾는다. vertex 하나도 하나의 tree이다.
그 edge가 light edge이면 safe edge이다.
safe edge를 set A의 forest에 추가해 나간다.

탐욕적인 방법(Greedy method)이다.

사이클을 이루지 않도록 최소 weight edge를 하나씩 선택해서 모든 vertex가 다 포함되면 minimum spanning tree가 된다.

구현
disjoint-set 이용.
vertex set을 만든다. edge들을 정렬한 다음 제일 작은 edge부터 선택한다. 선택된 edge가 사이클을 안만드는 것이어야 한다. edge (u,v)에서 u와 v를 find-set(x)해서 두개 값이 똑같으면 같은 set에 있다는 거니까 다른 값이 나와야 한다. 다르면 union한다.

성능
disjoint-set의 구조에 따라 성능 차이가 있다. union-by-rank와 path-compression을 이용하면 빠르다.
Edge수를 m, Vertex 수를 n이라 하면
1. set 초기화 Θ(n)
2. edge 정렬  Θ(m lg m),
3. find, equal, merge는 Θ(lg m), 이것을 모든 Edge에 대해 반복하므로 Θ(m lg m)이다.
m >= n-1이기 때문에 2,3 번이 1번을 지배. 따라서 Θ(m lg m)
최악의 경우 완전그래프일 경우 edge의 개수는 m=n(n-1)/2. 따라서 시간복잡도가 (n^2lg n)

Greedy method를 사용해서 값을 구하면 이게 정말 optimal solution인지 확인해야 한다.


2. Prim algorithm 
마찬가지로 탐욕적인 방법.
set A는 언제나 하나의 tree이다.(Kruskal은 forest)
set A와 연결되는 light edge 구하기. set A와 나머지를 나누는 선을 긋고, 그 선을 지나는 최소 edge중 하나가 light edge.
root vertex에서 시작한다.

구현
Minimum spanning tree를 A라고 하자.
모든 노드를 우선순위큐에 넣고
최소 key를 가진 vertex를 꺼낸다. (처음에 초기화할 때 루트의 key가 0이고 나머지는 다 무한대로 설정해서 처음에 루트가 꺼내져서 A에 들어간다.) 꺼낸 vertex(u)의  인접 vertex(v) (큐에 아직 남아있는 것)만 탐색하여 v의 키값이 (u,v) edge의 weight 값보다 크다면 key값을 weight 값으로 변경한다. 그리고 부모노드를 u로 설정한다. 큐가 비워질 때까지 이 과정을 반복한다.

성능
큐에 vertex가 없을 때까지 while문 반복, |V|번. (V는 vertex수)
큐에서 최소값 뽑는 것이 O(lg V).
while 다 돌면 큐에서 모든 vertex를 뽑으니까 O(V lg V) ----------1번

그래프의 인접리스트의 총 edge 길이는 2|E| (undirected graph, E는 edge 수)
그래서 큐에서 vertex 뽑고 그 vertex의 인접리스트를 탐색하는 거 O(E).
탐색 과정에서 vertex가 큐에 있는지 확인하고 있으면 key값 변경하고, 부모노드 설정.
큐에 있는지 확인하는 것은 vertex에 bit하나를 할당하여 큐에 있는지 없는지 상태를 나타내면 큐를 다 뒤지지 않고도 상수시간에 큐에 존재여부를 확인 할 수 있다.
부모노드 설정도 상수시간.
그리고 key값 변경하는 것은 min-heap에서 Decrease-key랑 같은거다.(key값 변경하고 min-heap이 유지되도록 변경된 vertex의 트리에서의 위치를 찾는 것) O(lg V)이다.
따라서 인접리스트 탐색하면서 key값 변경하는 시간은 O(E lgV) ----------2번
1,2번에 의해 total time은 O(V lg V + E lg E) = O(E lg V)

Fibonacci heap을 통해 성능향상을 할 수 있다.

Greedy method를 사용해서 값을 구하면 이게 정말 optimal solution인지 확인해야 한다.

'공부 > 알고리즘' 카테고리의 다른 글

Single-Source Shortest Paths  (0) 2011.07.13
Elementary Graph Algorithms  (0) 2011.07.13
Data Structures for Disjoint Sets  (0) 2011.07.11
Greedy Algorithms  (0) 2011.07.11
Dynamic Programming  (0) 2011.07.09


Posted by skyjumps