크루스칼

크루스칼 알고리즘

0. 최소 신장 트리 신장트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이크이 존재하지 않는 부분 그래프(트리) 최소신장트리 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘 적용 예시 1. 도시간 최소 거리 구하기 2. 서버간 최서 거리 구하기 1. 서로소 집합 서로소 집합 공통원소가 없는 두 집합 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 트리 자료구조를 이용하여 집합 표현 주요 연산 1. Union(합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 두 노드 A, B확인 A의 루트노드 root(A), B 루트노드 root(B)를 찾음 root(A)를 root(B)의 부모 노드로 설정(root(..