kruskal

크루스칼 알고리즘(kruskal)

📔 크루스칼(kruskal) 이란 간선을 하나씩 선택해서 MST를 찾는 알고리즘 ( 프림은 정점을 선택, 크루스칼은 간선을 선택 ) 최초 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다 사이클이 존재하면 패쓰 ( 사이클의 존재를 파악하는게 중요! ) V-1개의 간선이 선택될 때 까지 반복 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 disjoint-set 알고리즘을 이용한다. 📔 크루스칼(kruskal) 구현 def make_set(x): p[x] = x def find_set(x): if p[x] == x: return x else: p[x] = find_set(p[x]) return p[x] def union(x, y): px ..