최소신장트리2 [kotlin, 프로그래머스] 최소신장트리 문제와 입출력최소 신장 트리 (Minimum Spanning Tree, MST)의 정의와 특징정의최소 신장 트리는 가중치가 할당된 무방향 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소가 되는 트리입니다.특징트리의 간선 수: (V - 1)개의 간선을 가집니다.사이클 없음: 트리 구조이므로 사이클을 형성하지 않습니다.가중치 최소화: 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되어야 합니다.사용 예통신 네트워크 구축: 노드들을 가장 적은 비용으로 연결할 때 사용됩니다.최소신장트리(MST) 구현 방법 - 크루스칼 알고리즘, 프림 알고리즘 사용 크루스칼간선을 가중치 순으로 정렬 후, 작은 것부터 선택 (사이클 방지)간선 정렬 + 유니온 파인드 (Union-Find)프림정점 기준으로, 현재 트리.. 2025. 4. 12. [그래프 알고리즘] 크루스칼 알고리즘 Kruskal Algorithm 그래프 알고리즘이란, 그래프와 같은 복잡하고 연결성이 높은 자료구조에서순회 (Graph Traversal), 탐색 및 검색 (Graph Search) 등과 같은 목적으로 사용되는 알고리즘이다. 신장 트리란, 그래프 내의 모든 정점을 포함하는 트리로, 최소의 간선으로 모든 정점이 연결되어 있는 순환성이 없는 부분 그래프이다. 최소 신장 트리 알고리즘이란,최소 신장 트리란 그래프 내의 여러 신장 트리 중 가중치가 최소가 되는 신장 트리를 말하며, 최소 신장 트리 알고리즘은 그래프 내의 최소 신장 트리를 찾는 알고리즘이다.각 엣지에 가중치가 부여된 무방향 그래프에서 만들어지는 신장 트리중 가중치의 합이 가장 작은 신장 트리를 특별히 최소 비용 신장 트리(minimum cost spanning tree)라고 .. 2024. 8. 5. 이전 1 다음
