성장하고 개발하는 계란의 이야기

개념 최소 신장 트리 아래 링크 참조  [알고리즘]크루스칼 알고리즘(kruskal's Algorithm) 정리개념 최소 신장 트리(MST,  Minimum Spanning Tree)연결된 무방향 가중치 그래프에서 모든 정점을 포함하면서, 가중치의 합이 최소가 되는 트리  위 내용은 gpt가 설명하는 MST의 정의입니다. 두 정점 사growingegg.tistory.com 프림 알고리즘   최소 신장 트리를 찾기 위해 사용되는 알고리즘. 트리에 포함된 정점을 제외한 나머지 정점과의 간선 중 가중치가 가장 작은 간선을 선택하는 방식  아래와 같은 그래프가 있다고 가정하겠습니다. 1 번 정점부터 시작으로 간선을 확인합니다. 트리에 포함된 정점은 주황색으로 표시하였습니다. 1번에 연결된 간선은 1 - 3과 1 ..

개념 최소 신장 트리(MST,  Minimum Spanning Tree)연결된 무방향 가중치 그래프에서 모든 정점을 포함하면서, 가중치의 합이 최소가 되는 트리  위 내용은 gpt가 설명하는 MST의 정의입니다. 두 정점 사이의 간선이 서로 다른 가중치를 가지는 그래프에 대하여 최소 신장 트리는 다음과 같은 특징을 만족합니다. 모든 정점을 포함사이클이 없음 간선의 가중치 합이 최소 아래 그래프를 예시로 들어보겠습니다.  위 그래프에서 최소 신장트리는 다음과 같습니다. 최소 신장 트리를 구하는 대표적인 알고리즘은 크루스칼과 프림 알고리즘이 있습니다. 이번 게시물에서는 그 중 크루스칼에 대해 알아보고자 합니다.  크루스칼 알고리즘(kruskal's Algorithm)간선을 가중치 순(오름차순)으로 정렬한 후..