[그래프] 최소 신장 트리 minimum spanning tree

신장트리는 그래프에서 사이클이 생기지 않고 모든 노드가 연결될 수 있게 최소한의 간선만 남긴거다.

각 엣지가 cost를 가질 때 이 cost 합이 최소한이 되도록 신장트리를 만드는 알고리즘이 kruskal 알고리즘이다.

그리고 그러한 신장트리를 최소신장트리라고 한다.

 

최소신장트리는 모든 엣지를 작은순으로 정렬해놓고

사이클이 안생기면 그 엣지를 확정짓는 방식으로 만든다.

이때 사이클이 생길지 안생길지 여부를 살펴보는데에 disjoint set이 쓰이는데 (union find)

두 노드의 루트노드가 같으면 두 노드를 연결했을 때 사이클이 생기는 걸 이용해 검사한다.

 

class disjoint_set:
    def __init__(self, num_of_elements):
        self.parent = [i for i in range(num_of_elements)]

    def find(self, element_index):
        if self.parent[element_index] == element_index:
            return element_index
        
        parent_index = self.find(self.parent[element_index])
        self.parent[element_index] = parent_index
        return parent_index

    def union(self, element1_index, element2_index):
        parent1 = self.find(element1_index)
        parent2 = self.find(element2_index)

        self.parent[max(parent1,parent2)] = min(parent1,parent2)

    def print_parent(self):
        print("parent list",self.parent)

    def is_disjoint(self, element1, element2):
        parent1 = self.find(element1)
        parent2 = self.find(element2)

        return parent1 != parent2


v, e = map(int, input().split())
ds = disjoint_set(v)

edges = []
for i in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost,a,b))

edges.sort()

min_cost = 0

for cost,a,b in edges:
    if ds.is_disjoint(a,b):
        ds.union(a,b)
        min_cost += cost

print(min_cost)