[알고리즘] 크루스칼 알고리즘

정의

• Spanning Tree, 최소 비용 신장 트리를 O(ElogV)O(ElogV)만에 구하는 알고리즘이다.
• 신장 트리의 조건
  • 본래의 그래프의 모든 노드를 포함해야함
  • 모든 노드가 서로 연결
  • 트리의 속성 만족 (사이클 존재하지 않음)

코드

parent = {}
rank = {}

def find(node):
	if parent[node] != node:
		parent[node] = find(parent[node])
	return parent[node]   

def union(node_v, node_u):
	
	root1 = find(node_v)
	root2 = find(node_u)
	
	if rank[root1] > rank[root2]:
		parent[root2] = root1
	else:
		parent[root1] = root2
		if rank[root1] == rank[root2]:
			rank[root2] += 1 
			
def make_set(node):
	parent[node] = node
	rank[node] = 0            


def kruscal(n, costs):
	
	mst = list()	
	for node in range(n):
		make_set(node)          
		
	costs.sort(key=lambda k:k[2])
	
	for node_v, node_u, cost in costs:
		if find(node_v) != find(node_u):
			union(node_v, node_u)
			mst.append((node_v, node_u, cost))
	
	min_v = sum([v[2] for v in mst])        
	return min_v


n = 4
costs = [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
result = kruscal(n, costs)
# mst: [(0, 1, 1), (1, 3, 1), (0, 2, 2)]
# result: 4

n = 5
costs = [[0,1,5],[1,2,3],[2,3,3],[3,1,2],[3,0,4],[2,4,6],[4,0,7]]
result = kruscal(n, costs)
# mst: [(3, 1, 2), (1, 2, 3), (3, 0, 4), (2, 4, 6)]
# result: 15