[자료구조 및 알고리즘] #19 - Greedy Algorithms (2)

0.

 

2024.09.12 - [학교 수업/자료구조 및 알고리즘] - [자료구조 및 알고리즘] #18 - Greedy Algorithms

[자료구조 및 알고리즘] #18 - Greedy Algorithms

앞서 살펴봤던 Prim Algorithm과 같이 MST를 구하는 또 다른 알고리즘,

Kruskal Algorithm을 살펴보려고합니다.

2024.06.09 - [학교 수업/자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application

자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application

 

1. Kruskal algoritm correctness

 

Kruskal알고리즘에 대한 설명은 위 글에 너무나 잘 설명해놨기 때문에 넘어가고,

정확성에 대한 증명을 해보겠습니다.

 

Prim알고리즘의 증명과 비슷한 증명을 사용합니다.

 

임의의 정답 MST인 Tmst를 가정하고,

Kruskal알고리즘이 만들어나가는 MST인 T와 비교했을 때,

Tmst에 모순이 있고, T가 맞다는 것을 증명하면 Kruskal알고리즘의 정확성이 증명됩니다.

 

아래는 kruskal의 정답이라고 가정할 MST인 Tmst입니다(* 이는 정답이 될 수도 아닐 수도 있습니다.):

Tmst

 

또 아래는 kruskal알고리즘에 따라 만들어지고 있는 Tree인 T입니다:

T

 

만약 T가 만들어지고 있는 과정 (f)에서 (f)의 다음단계로 선택해야하는 간선인 edge(3,4)가 아닌 다른 간선을 선택했다고 가정합니다.

 

edge(3,6), edge(3,1) 이런것들은 cycle이 만들어지기 때문에 애초에 선택하지 않을것이고, edge(3,5)를 선택했다고 가정합니다. 간선 edge(3,5)를 e라고 하고, 원래 선택했어야 했을 간선인 edge(3,4)를 포함하여 {Tmst ∪ {e}} 에서 cycle이 만들어지는 간선들 중 하나를 e'이라고 합니다. 우리의 예시에서는 edge(3,4)를 e'이라고 가정합니다.

(* Prim과 다르게 e'이 cycle을 만드는 간선들 중 아무거나 될 수 있습니다.)

 

이때 3가지의 경우의 수가 생깁니다:

• w(e) < w(e'): Tmst는 MST가 아닙니다. {Tmst - {e'}} ∪ {e}가 전체 weight도 적고 모두 연결할 수 있는 MST이기 때문입니다. 따라서 T가 MST가 됩니다.
• w(e) = w(e'): Tmst와 T모두 정답입니다. MST는 하나의 그래프에서 여러 개가 나올 수 있기 때문에 가능합니다.
• w(e) > w(e'): kruskal알고리즘이 정확하다면 일어날 수 없는 일입니다. kruskal알고리즘에 따르면 아직 선택하지 않은 간선들 중 가중치값이 가장 작은 간선을 선택할텐데, e'의 가중치가 e보다 작다면 e대신 e'을 선택했을 것입니다. 즉, 일어날 수 없는 일입니다.

따라서 kruskal알고리즘을 제대로 따라가기만 하면, MST가 만들어짐을 알 수 있습니다.

 

앞서 kruskal알고리즘을 설명한 글에서도 말했듯이,

kruskal알고리즘을 구현하는 데에는 union-find/disjoint set의 구현이 필수적입니다.

 

Prim알고리즘의 경우는 cycle이 만들어지는 여부를 '이전 방문한 노드는 선택하지 않는다'고 규칙을 만들면 되지만,(* 하나의 노드에서 트리를 키워나가는 형식이기 때문에 트리 그룹 자체가 커지는 형태입니다.)

 

Kruskal알고리즘의 경우는 각자의 트리 그룹이 점점 커지면서 하나로 합쳐지는 형태이기 때문에, 그룹끼리의 cycle형성 여부를 확인해야합니다. 따라서 이를 빠르게 해결하기 위한 union-find/disjoint set이 필수적입니다. 또한 시간복잡도가 상수시간정도이기 때문에 더욱 더 사용해야 합니다.

 

2. Time complexity

 

정점의 개수가 N이고, 간선의 개수가 M일 때,

O(mlogm)입니다.

간선의 개수(* M)만큼 반복하는데, 한 번 할때마다 PQ에서 정렬(* logM)하기 때문입니다.

 

disjoint set에서 cycle의 형성 여부를 확인하는 것은 상수시간에 가깝기 때문에,

big O notation에 의해 고려하지 않습니다.

 

3. MST의 개수

 

앞서 증명에서 봤듯이,

w(e)와 w(e')이 같은 경우 여러 개의 MST가 있을 수 있음을 말했습니다.

그렇다면 이를 통해 하나의 그래프에서 MST가 최대 몇 개가 만들어질 수 있는지를 알 수 있을까요?

 

Prim의 경우,

알고리즘을 진행하다가 선택지가 되는 간선들의 가중치가 똑같은 경우, 당연히 그 간선들을 추가했을 때 cycle이 형성되서는 안됩니다.

그 간선들을 선택하는 기준이 없습니다.

 

Prim알고리즘은 그냥 가중치가 가장 작은 간선을 선택하면 되는것이지, 가중치가 가장 작은 간선이 여러개이면 어떤 것을 선택하라는 규칙은 없습니다. 따라서 선택할 수 있는 간선의 개수만큼 MST가 될 수 있는 경우의 수가 늘어나는 것입니다.

 

Prim알고리즘을 따르면 일단 MST가 되는 것은 정확하기 때문에,

알고리즘에 모순되지 않는 한, 여러개의 선택을 할 수 있습니다.

 

Kruskal도 마찬가지입니다.

선택지가 되는 간선들 중 가장 가중치가 작은 간선들을 선택하기만 하면 됩니다. 그 간선들 중 어떤 것을 고르라는 것은 없기 때문에 Kruskal알고리즘을 진행하면서 생기는 선택지만큼 MST의 개수는 점점 늘어가는 것입니다.(* 당연히 cycle이 생겨서는 안됩니다.)