데브카이브 데브카이브

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

신장 트리 (Spanning Tree)신장 트리는 다음과 같은 특징을 가진다.그래프의 모든 정점을 포함한다최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)트리이기에 사이클을 가지지 않는다 위와같은 그래프가 있다고 할때 다음과같이 여러개의 신장 트리들이 나올 수 있다.  위의 예시 외에도 더 다양한 형태의 신장 트리가 존재한다.최소 신장 트리 (Minimum Spanning Tree)최소 신장 트리의 개념은 간단하다. 그래프의 존재하는 신장 트리중 가중치의 합이 가작 작은 신장 트리가 최소 신장 트리이다.위의 예시에서는 왼쪽부터 차례대로 가중치의 합이 12, 16, 18 이다. 그 외에도 존재하는 신장 트리중 가장 작은 가중치의 합을 가진 최소 신장 트리는 아래의 트리이다. ..