알고리즘 기초 - 크루스칼 알고리즘(최소 신장 트리)
·
My Study/Algorithm
- 크루스칼(Kruskal) 알고리즘이란? 크루스칼 알고리즘에 대해 설명하기 전, 서로소 집합 연산과 신장 트리에 대해 알아야 합니다! 그럼 각각에 대한 개념을 설명하겠습니다. 1) 서로소 집합 서로소 집합이란! 수학적 의미 그대로 공통 원소가 없는 두 집합을 의미합니다. 두 개의 집합이 주어졌을 때 겹치는 요소들이 하나도 없어야 합니다. 두 집합이 서로소인지 판별하는 알고리즘은 다음과 같습니다. 1. 합집합 연산(union)을 통해 서로 연결된 두 노드 A와 B를 확인합니다. => A와 B의 루트 노드 A'과 B'을 각각 찾습니다. => A'를 B'의 부모 노드로 설정해줍니다. 2. 모든 합집합 연산을 처리할 때까지 1번 과정을 계속 반복해줍니다. 이 서로소 집합 연산을 이용한다면 무방향 그래프에서..