데브카이브 데브카이브

서론최소 신장 트리(이하 MST)를 구하는 프림 알고리즘을 알아보자. 최소 신장 트리에대한 설명이 필요하다면 아래 글을 참고하도록 한다.2024.08.13 - [알고리즘] - 최소 신장 트리 최소 신장 트리신장 트리 (Spanning Tree)신장 트리는 다음과 같은 특징을 가진다.그래프의 모든 정점을 포함한다최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)트리이기에 사이클을 가devchive.tistory.com 프림 알고리즘프림 알고리즘은 다음과 같은 순서를 가진다.임의의 정점을 선택해 MST에 추가한다MST에 포함된 정점과 포함되지 않은 정점을 연결하는 간선 중 가장 비용이 적은 간선을 선택해 MST에 추가한다최소 신장 트리에 V - 1개의 간선이 추가될 때 까지 2번..