반응형 Minimun Spanning Tree1 [알고리즘] 크루스칼(Kruskal)과 프림(Prim) Goal MST란? 크루스칼이란? 프림이란? 최소 신장 트리에 사용된 최소 비용을 어떻게 구할까? 최소 비용으로 신장 트리를 어떻게 만들 수 있을까? 1. 크루스칼? 프림? MST? 1) MST(Minimum Spanning Tree) 신장 트리(Spanning Tree) 무방향 그래프 G(V,E)에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프를 신장 트리(Spanning Tree)라 한다. 그래프에서 신장 트리는 여러 형태로 존재할 수 있으며, 신장 트리의 특징은 n개의 정점을 갖는 그래프에서 신장 트리에 속하는 간선의 수는 n-1개이며 사이클을 이루지 않는다는 특징이 있다. MST란 최소 비용 신장 트리(이하 최소 신장 트리)를 뜻하며, 무방향 그래프의 간선들에.. 2021. 12. 15. 이전 1 다음 반응형