[알고리즘] CHAP 4. GA - Kruskal's algorithm (크루스칼 알고리즘)

지난 게시글에 이어 이번에는 Greedy Approach 중에서 Kruskal 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다

• Kruskal 알고리즘
  
  • 접근방식
  • 코드
  • 시간복잡도

Greedy Approach와 프림 알고리즘은 아래 링크를 참고하도록 하자!

https://wanna-developer02.tistory.com/51

[알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘)

---

1. Kruskal algorithm (크루스칼 알고리즘)

크루스칼은 프림 알고리즘과 마찬가지로 가중치가 가장 작은 간선을 선택하면서, 사이클을 만들지 않는 (MST) 알고리즘이다. 프림과는 알고리즘이 살짝 다르다.

 

# 접근방식

1. 간선을 가중치 기준으로 오름차순 정렬을 한다.

2. 위에서부터 선택을 하되 사이클을 만들지 않는 선에서 선택한다.

3. 노드의 개수를 n이라고 하면, 간선이 n-1개 선택되었을 때 종료한다.

 

크루스칼 알고리즘

 

# Code

weight = [(0,1,9), (0,2,10), (5,6,6), ... , (2,5,2)] // 예시
weight.sort(key = lambda t : t[2]) // idx가 2인 거 기준으로 오름차순 정렬

mst = []
N = 7
p = [] * N
for i in range(N) :
	p.append(i)  // 간선 정보 담기 (처음에는 자기자신으로 세팅)
    
def find(u) : // 사이클 방지 경로압축
	if u != p[u] :
    	p[u] = find(p[u])
    return p[u]
    
    
def union(u,v) :
	root1 = find(u)
    root2 = find(v)
    p[root2] = root1
    

tree_edge = 0 // 간선개수
mst_cost = 0  // 가중치 합

while True:
	if tree_edge == N - 1 :
    	break
    u, v, wt = weight.pop(0)
    
    if find(u) != find(v) :
    	union(u, v)
        mst.append((u, v))
        mst_cost += wt
        tree_edge += 1

 

위 코드에서 find는 사이클생성을 막기 위해 경로를 압축하는 코드이다.

 

find를 수행한 후 결과값이 서로 다르면 사이클을 만들지 않는다고 이해하면 된다.

 

 

#  Time Complex

 노드 개수가 n, 간선 개수가 m이라고 할 때, loop 시간은 θ (m lg m) 이다.

 

Worst time Complexity의 경우, m = n(n-1) / 2 ∈θ (n^2) 이므로, θ (n^2 lg n^2) =θ (n^2 lg n) 이 된다.