Loading [MathJax]/jax/output/CommonHTML/jax.js
본문 바로가기
반응형

Kruskal1

[Coding Test][Python][Shortest Path] Kruskal 알고리즘 개념 및 예제, Union - Find 자료구조 1. Kruskal 알고리즘이란?그래프의 Minimum Spanning Tree(MST, 최소 신장 트리) 를 구하는 대표적인 알고리즘입니다.Minimum Spanning Tree란 그래프의 모든 Vertex가 연결하면서 Edge의 Weight의 합이 최소가 되는 Tree를 의미합니다.알고리즘 특징Edge를 중심으로 접근하여 MST를 구성Greedy 알고리즘 사용Undirected Weighted Graph에 적용가능시간 복잡도 : O(ElogE)2. Kruskal 알고리즘 동작 과정위의 그래프에서 Kruskal 알고리즘을 적용해보겠습니다.1) 모든 Edge를 가중치가 작은순으로 정렬Edge의 Weight가 작은 순으로 정렬한 후 가장 작은 Weight를 가진 Edge를 선택합니다.2) 정렬된 E.. 2025. 3. 18.
반응형

티스토리툴바