union by rank1 최소 스패닝 트리(Minimum Spanning Tree) 알아보기 +) 그 전에 스패닝 트리란?※ 그래프 내 모든 정점을 포함하는 부분 그래프. 최소 스패닝 트리란? (Minimum spanning tree)혹은 Minimum Weight Spanning tree (최소 가중치 스패닝 트리)라고도 불림.가중 + 무방향 그래프의 모든 정점을 연결하면서 사이클을 이루지 않음 + 그래프를 이루는 모든 가중치의 합이 최소인 트리를 말함. 특징그래프 내 N개의 정점이 있다고 할 때, 각 스패닝 트리는 N-1개의 간선을 가진다.한 그래프 내에는 여러 개의 최소 스패닝 트리가 존재할 수 있다.만약 그래프 내 모든 간선의 가중치가 같다면, 모든 스패닝 트리는 항상 최소의 가중치 합을 가진다. 알고리즘프림 알고리즘주어진 그래프에서 한 정점을 선택하여 트리를 만듦.그래프의 모든 간선이 .. 2024. 8. 4. 이전 1 다음