목록최소 신장 트리 (1)

programmingu

최소 신장 트리(MST) - Kruskal , Prim

최소 신장 트리(MST) 그래프의 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 찾기! 어디에서 시작하는 지 상관없이 모든 정점이 다 이어질 수 있도록 팔을 뻗는다고 생각하면 된다. 간선이 적을 때 => KRUSKAL(간선 중심) 간선이 많을 때 => PRIM(정점 중심) Kruskal 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 모든 간선을 가중치에 따라 오름차순으로 정렬 (최초 한번) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 *** 사이클을 형성하는 간선은 선택 x!** ⇒ union-find 알고리즘을 이용한다. n-1 개의 간선이 선택될 때까지 반복해서 선택 사이클을 형성하는 방법 ⇒ union-find 추가하고자하는 간선의 양끝 정점이 같이 집합에 속해있..
Computer Science/알고리즘 2021. 12. 14. 01:47
이전 Prev 1 Next 다음