프림
-
[알고리즘 정리] Kruskal & Prim(크루스칼과 프림)Development/Algorithm 2020. 5. 3. 20:59
다룰 내용 신장 트리란 무엇인가? 최소 비용 신장 트리란 무엇인가? 최소 비용 신장 트리를 구성하는 방법 Kruskal 알고리즘 Prim 알고리즘 신장 트리란 무엇인가? 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말합니다. 사이클이 안 생기는 조건 안에서 간선의 개수를 정점 - 1개로 골라 만드는 것으로, 정점 - 1의 수가 간선의 수가 되는 트리입니다. 최소 비용 신장 트리란 무엇인가? 신장 트리 중에서 간선들의 합이 최소인 트리입니다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며 비용의 합이 최소인 트리입니다. 최소 비용 신장 트리의 특징 무방향 가중치 그래프입니다. 가중치의 합이 최소입니다. 정점 n개에서 n - 1개의 간선을 가지는 트리입니다. 사이클이 포..