hyunkookim 님의 블로그

Prim's AlgorithmSolved HardImplement Prim's minimum spanning tree algorithm.A Minimum Spanning Tree (MST) is a tree that spans all the vertices in a given weighted, undirected graph while minimizing the total edge weight and avoiding cycles. It connects all nodes with exactly ∣V∣−1∣V∣−1 edges, where VV is the set of vertices, and has the lowest possible sum of edge weights.Prim's algorithm is a ..

✅ 1. 최소 신장 트리(Minimum Spanning Tree)란?정의: 주어진 무방향 연결 그래프에서 모든 정점들을 연결하면서 가중치의 합이 최소가 되는 트리 구조의 부분 그래프.조건모든 정점이 연결되어 있어야 함.사이클(순환)은 없어야 함.여러 개의 MST가 존재할 수도 있음.📌 기본 개념Undirected Graph (무방향 그래프)모든 노드가 연결되도록 (Connected)전체 간선의 가중치 합이 최소가 되도록 (Minimum Total Cost)노드가 n개라면 MST는 항상 n - 1개의 간선만 포함→ 그래서 사이클이 생기지 않음어느 노드에서 시작해도 결과는 동일한 MST 완성 가능✅ 2. Prim's Algorithm이란? (프림 알고리즘)핵심 아이디어: 하나의 정점에서 시작해서, 가장 작..