08. kruskal algorithm [3 2주차]

8. Kruskal Algorithm [3-2주차]

2024년 1월 9일 화요일

오후 11:12

<Kruskal Algorithm>

하나의 노드에서 시작해 점차 확장해 나가는 Prim과 달리, 그래프 전체를 보고 가장 작은 간선을 추가. 알고리즘 수행 과정에서 하나의 트리가 아니라 여러 덩어리가 생기게 된다. (노드 하나도 덩어리 하나로 본다)

 

추가된 간선이 서로 다른 덩어리를 연결한 경우, 덩어리 개수는 무조건 감소한다.

즉, 간선을 추가했을 때 덩어리 개수가 줄어들지 않은 경우, 같은 덩어리 안의 노드를 연결했다는 것. 사이클이 생기게 된다.

-> 크루스칼 알고리즘에서는 같은 덩어리 안에서 연결하는가, 다른 덩어리끼리 연결하는가를 판단하여 사이클 생성 여부를 확인한다. 같은 덩어리 안의 노드를 연결하는 간선은 MST에 추가하지 않는다.

 

 

 

<Kruskal Algorithm의 증명>

하나의 정답 T_mst0 가 있다. 크루스칼 알고리즘이 이전까지 간선 집합 S을 선택하였고, 방금 (a, b)를 추가로 선택하였다. (S는 T_mst0의 부분집합이라 가정)

 

S' = S U {(a, b)} 에서 (a, b)가 T_mst0의 원소가 아니라면?

T_mst0 U {(a, b)}에서 (a, b)는 사이클을 형성하게 됨.

크루스칼에서 추가되었으므로, S에서 a와 b는 다른 덩어리에 있어야 함.

T_mst0내에서, a에서 b로의 경로 내에 S에 포함되지 않는 간선이 존재해야 함. 그렇지 않으면 a와 b가 다른 덩어리에 있다는 것에 모순.

그 간선을 (x, y)라 하자.

prim알고리즘 증명과 마찬가지 이유로 w(a,b) = w(x,y).

따라서 T_mst0에서 (x,y)를 빼고 (a, b)를 추가한 트리도 최소 신장 트리.

 

 

<구현 및 성능>

Algorithm Kruskal(G ,T)

T <- empty set

E를 가중치 오름차순 정렬

V개의 노드마다 Disjoint Set을 만듬

 

while |T| < |V| - 1

E에서 가장 작은 weigh인 에지 (u, v) 선택

E = E - {e}

 

if find(u) != find(v)  // 사이클이 생기지 않으면

T = T U {e}

union(u, v)

 

 

노드가 어떤 덩어리에 있는지를 파악하기 위해 Union Find (Disjoint Set)를 사용.

 

 

<Union Find (Disjoint Set) >

노드 하나는 data와 parent 멤버 변수를 가진다.

data는 실제 데이터를 가리키는 포인터이고, parent는 부모 노드를 가리키는 포인터이다.

 

find(A) : A노드의 대장 노드를 리턴. 대장 노드는 최고 조상 노드를 의미. parent가 null이 나올 때까지 타고 올라가서 구함.

 

union(A, B) : A와 B가 속해 있는 집합을 합친다. B의 대장 노드의 부모를 A의 대장 노드로 설정하면 된다.

 

 

find(A)==find(B) 이면 A 와 B는 같은 집합에 있다.

 

원소가 n개일 때, find와 union의 연산 속도는 점근적으로 매우 빠르다. -> O(a(n))

여기서 a(n)은 log보다도 느리게 증가하는 함수이다.

 

 

<Kruskal의 성능>

E를 정렬하는 데 O(ElogE) 시간이 걸림.

Disjoint Set을 만드는 데 O(V)가 걸림.

 

while 문은 최대 E번 실행됨.

최소 가중치 간선 선택은 O(1), 총 O(E)가 걸림.

 

find 연산은 2E * O(a(V)) = O(E * a(V)) 가 걸림.

union 연산은 (V-1) * O(a(V)) = O(V * a(V)) 가 걸림.

|E| >= |V| - 1 이므로, find와 union연산은 총 O(Ea(V)) 가 걸림.

 

따라서 크루스칼 알고리즘의 전체 수행 시간은

O(ElogE) 이다.

 

 

<Prim과 Kruskal 알고리즘은 모든 답을 찾을 수 있다>

가중치가 같은 간선이 있으면 답이 여러 개 나올 수도 있다.

그러나 가중치가 같은 간선이 없으면 답이 하나밖에 안 나온다.

(가중치 1, 4를 포함하고 2, 3이 포함되지 않는 답은 존재하지 않는다. 무조건 1, 2가 포함된다.)

Prim, Kruskal 알고리즘이 모든 답을 찾을 수 있다는 것으로부터 이를 증명할 수 있다.

 

실제로 알고리즘을 짤 때 같은 가중치의 간선 중 어떤 걸 추가할 지, 어떤 노드부터 시작할지에 따라 답이 달라질 것이다. 그러나 어떻게 알고리즘을 구현해도 (여러 답 중) 나오지 않는 답이 있지 않을까? 그렇지 않다.

Prim, Kruskal 알고리즘은 모든 답을 찾을 수 있다.

 

증명

임의의 답 T_mst를 정하고, Prim알고리즘이 그 답을 찾을 수 있다는 것을 보이자.

알고리즘이 T_mst에 존재하지 않는 간선 (u, v)를 선택하였다고 가정한다.

Prim 알고리즘 증명에서 w(u, v) = w(x, y)임을 증명했다.

(간선 (x, y)는 이전까지 선택한 트리에 붙어 있고, T_mst에 포함되는 간선이였음을 기억하자)

Prim 알고리즘이 (u, v)대신 (x, y)를 선택할 수도 있을까? 코드를 어떻게 짰는지에 따라 충분히 가능하다. ex) 선택 가능한 간선을 모두 모아놓고 랜덤하게 선택.

 

위 증명을 통해 모든 가중치가 다르면 답이 하나뿐이라는 것을 증명할 수 있다.

T_mst에서 벗어나는 경우는 w(u, v) = w(x, y)인 경우뿐. 가중치가 모두 다르면 그런 경우가 없다. 따라서 Prim 알고리즘은 T_mst만을 찾아낼 수 있다. Prim알고리즘은 모든 답을 찾아낼 수 있으므로, 답이 하나뿐.