Introduction
Coddy의 크루스칼 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 1번째.
그래프 알고리즘(Graph Algorithms) 시리즈에 다시 오신 것을 환영합니다! 최소 신장 트리(Minimum Spanning Tree, MST)는 가중치 그래프의 모든 정점을 사이클 없이 가장 저렴한 총 간선 가중치로 연결합니다.
크루스칼 알고리즘(Kruskal's Algorithm)은 탐욕적(greedy) 방식으로 MST를 구축합니다. 간선을 가장 저렴한 것부터 가장 비싼 것 순으로 정렬하고, 사이클을 생성하지 않는 한 각 간선을 추가합니다. 사이클을 빠르게 감지하는 비결은 유니온 파인드(union-find)(서로소 집합(disjoint-set)이라고도 함)라고 불리는 자료 구조입니다.
그래프는 무방향 가중치 그래프이며, n(정점 0부터 n - 1까지)과 가중치 w인 무방향 간선 u - v에 대한 트리플 [u0, v0, w0, ...]의 평면 배열인 edges로 주어집니다.
시작해 봅시다!
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
