데브카이브 데브카이브

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

서론최소 신장 트리를 구하는 알고리즘은 크루스칼 알고리즘에 대해 알아보고 관련된 백준 1197 문제를 풀어보자.최소 신장 트리에대한 설명은 아래 글을 참고하자.2024.08.13 - [알고리즘] - 최소 신장 트리 최소 신장 트리신장 트리 (Spanning Tree)신장 트리는 다음과 같은 특징을 가진다.그래프의 모든 정점을 포함한다최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)트리이기에 사이클을 가devchive.tistory.com 크루스칼 알고리즘최소 신장 트리(이하 MST)를 구하는 크루스칼 알고리즘은 다음과 같은 순서를 가진다.간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다현재 선택한 간선이 정점 U,V를 연결하는 간선이라고 할 때, 만약 U..