크루스칼 알고리즘 (Kruskal's algorithm) 은 주어진 그래프에서 최소 신장 트리를 찾는다. 주로 그래프 내의 모든 정점을 최소 비용으로 연결하기 위해 사용한다. 간선의 개수가 E, 정점의 개수가 V 일 때 O(ElogV) 의 시간복잡도를 가진다. 모든 간선에 대해 (1) 가중치가 최소인 간선을 찾고, (2) 해당 간선으로 인해 사이클이 발생하지 않는다면 (Union-Find 활용) 두 정점을 연결한다.
Union-Find 는 상호 배타적인 집합을 효율적으로 표현하기 위한 자료 구조이다. 서로 다른 두 개의 집합을 병합하는 Union 연산과 어떤 원소가 속한 집합을 찾는 Find 연산으로 구성된다. 크루스칼 알고리즘에서 정점 간의 연결 여부를 판단하는 데에 사용한다.
📍 참고 자료
크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 E {\displaystyle E} , 꼭짓점의 개수를 V
ko.wikipedia.org
https://namu.wiki/w/%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
크루스칼 알고리즘
최소 비용 신장 트리 를 만에 구하는 알고리즘 이다. 구현방법 그래프의 모든 간선의 집합 을 만든다. 가 비
namu.wiki
https://namu.wiki/w/Union%20Find
Union Find
Union-Find(혹은 Disjoint Set)은 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어
namu.wiki
'기본' 카테고리의 다른 글
| [코딩테스트/Python] 프로그래머스 "체육복" (0) | 2024.03.27 |
|---|---|
| [코딩테스트/개념] 탐욕 알고리즘 (Greedy Algorithm) (0) | 2024.03.27 |
| [코딩테스트/Python] 프로그래머스 "퍼즐 조각 채우기" (0) | 2024.03.27 |
| [코딩테스트/Python] 프로그래머스 "아이템 줍기" (0) | 2024.03.26 |
| [PS | 문제 해설] BOJ 20921번 그렇고 그런 사이 (0) | 2021.02.24 |
