prim

최소 신장 트리(Minimum Spanning Tree)

그래프에서 최소 비용을 구하는 문제 1. 모든 정점을 연결하는 간선들의 가중치합이 최소가 되는 트리 - 프림과 크루스칼 두가지 형태가 있다. (프림은 정점을 기준으로, 크루스칼은 간선을 기준으로 MST를 만들어간다.) 2. 두 정점 사이의 최소 비용 경로 찾기 - BFS에서 가중치가 추가된 형태 신장 트리 1. n 개의 정점으로 이루어진 무방향 그래프에서 n 개의 정점과 n-1 개의 간선으로 이루어진 트리 최소 신장 트리 1. 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 그래프의 표현 1. 인접 행렬 2. 인접 리스트 🟨 프림 알고리즘: 프림 알고리즘은 하나의 정점에 연결된 간선중 가중치가 최소인 정점을 선택한다. 하나의 정점에서 연결된 간선들 중에 하나씩 선택..