Minimum SpanningTree(최소 비용 신장 트리)

Graph(그래프)와 Tree(트리)

그래프  : 정점(vertex)과 그 vertex를 연결하는 간선(edge)을 하나로 모아둔 자료구조

트리 : 그래프의 한 종류 ,Cycle이 불가능, undirected, connected,노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 

 

 

Weight Undirected Graph(가중 무방향성 그래프)

• 그래프(vertex,edge 로 이루어진 집합) + undirected (방향성을 가지지 않음) + 각 간선이 값을 가짐
• G=(V,E)
• 간선 집합에 속하는 각 간선 (u,v)는 w(u,v)를 가진다. 

 

Spanning Tree(신장 트리), Spanning Forest

Spanning Tree : 그래프에 있는 모든 vertex를 연결한 트리, 트리의 각각의 값을 모두 더한것을 spanning tree의 value라고 한다. 

Spanning Forest : 그래프가 연결되어있지 않아 Spanning Tree가 될 수 없을 때, 각각의 작은 spanning tree가 모여있는 것

 

Minimum Spanning Tree(MST)

MST

• 비용이 최소가 되는 신장트리를 찾는 문제
• 일반적인 MST : 한번에 하나의 간선을 늘리면서 safe인지를 확인한다. Cycle 이 생기는지 확인하고 없도록 만들어야함!!
•  MST는 유니크하지 않다. 여러개가 존재할 수 있다. 

• Greedy 알고리즘이다. 

        Optimal substructure를 만족한다.

        Greedy-choice를 만족한다. 

 

 

Prim’s MST Algorithm(프림 알고리즘)

• 각 단계에서 인접한 vertex중에 가장 작은 간선 값을 가지는 것(light edge)을 선택한다(cross). cut(A,V-A)가 되고 각각은 Greedy choice 만족
• cut(S,V-S) :무방향성 그래프에서 정점을 두개로 나눈 집합
• 간선 (u,v)의 끝점이 하나는 S에 있고 다른 하나는 V-S에 있는 경우, "간선 (u,v)가 cut(S,V-S)을 cross" 라고 한다.
• 프림 알고리즘의 단계

1. 집합에 속하는 간선은 항상 트리를 형성한다.
2. 트리는 임의의 root 정점 r에서 시작하며 V에 속하는 모든 정점을 포함할때까지 확장한다.
3. 각 단계에서는 light edge가 추가된다.
4. 알고리즘이 종료되면 최소신장트리가 만들어진다. 

Prim algorithm

 

• priority queue 사용(min-heap 이용)
• Runnung time : O(|E|log|V|)

 

Kruskal’s MST Algorithm(크루스칼 알고리즘)

그래프의 모든 edge를 정렬한 후 작은 값부터 추가해나간다. (loop 가 생기지 않게)

Greedy-choixe property이다. 

Implementation data structure : disjoint-set

 

Disjoint-Set

• A,B 가 disjoit -> A∩B={}=Ø =서로소 집합 = 상호 배타적인 집합들
• 서로 중복되지 않는 부분집합들로 나눠진 원소에 대한 정보를 저장하고 조작하는 자료구조
• 크루스칼 MST 알고리즘에서 새로 추가할 간선에 대해 cycle을 확인할 때 사용(양  끝 정점이 같은 집합에 속해있는지)
• Union-fine : disjoint set을 표현할 때 사용하는 알고리즘

1. make-set(x) : 초기화, x를 유일한 원소로 하는 새로운 집합을 만든다.
2. union(x,y) : 합치기, x와 y를 합친다. 즉, Sx∪Sy 이다. 
3. find(x) : 찾기, x가 속한 집합의 대표값(알파벳순서중 가장 앞의 값)을 반환한다. 즉 x가 어느 집합에 속해 있는지 찾는다.

 

크루스칼

• Running time : O(ElogV)

 

 

프림VS크루스칼

공통점 : 그리디 알고리즘이다. Runnung time이 O(ElogV)이다.

 

[차이점] 

프림 : 정점의 최선값을 선택하여 MST문제를 해결한다. heap 사용. 항상 트리 형성

크루스칼 : 간선의 가중치 값을 정렬하여 MST문제를 해결한다. disjoit-set 사용. forest 였다가 결과는 트리