탐욕적 기법 알고리즘 - KRUSKAL

최소비용 신장트리(MST) 문제에서 현재 선택할 수 있는 가중치 중 가장 작은 가중치를 가진 간선을 선택하는 방법(탐욕적인 해).

그와 동시에 간선을 추가했을 때 사이클이 생기면 안된다.

MST(minimum spanning tree)란 가중치 그래프 G = (V, E) 의 모든 신장트리 중에서 간선들의 합이 최소인 트리.

ex)  도시 10곳을 최소비용으로 모두 거치는 방법

 

 

# 서로소 집합
class disjoinSets:
	def __init__(self, n):
    	self.parent = [-1]*n
        self.set_size = n
        
    def find(self, id):
    	while(self.parent[id] >= 0):
        	id = self.parent[id]
        return id
        
    def union(self, s1, s2):
    	self.parent[s1] = s2
        self.set_size = self.set_size - 1

# Kruskal MST 알고리즘
def MSTKruskal(V, adj):
	n = len(V)
    dsets = disjoinSets(n)
    E = []
    for i in range(n-1):
    	for j in range(i+1, n):
        	if adj[i][j] != None:
            	E.append((i,j,adj[i][j]))
                
    E.sort(key = lambda e:e[2])
    
    ecount = 0
    for i in range(len(E)):
    	e = E[i]
        uset = dsets.find(e[0])
        vset = dsets.find(e[1])
        
        if uset != vset:
        dsets.union(uset, vset)
        print("간선 추가 : (%s, %s, $d)" % (V[e[0]], V[e[1]], e[2]))
        ecount += 1
        if ecount == n-1:
        	break