그리디1 [Algorithm] 최소 신장 트리(MST), Kruskal & Prim algorithm 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함한 최소 연결 부분 그래프이며 Tree이기 때문에 사이클이 존재할 수 없다. 최소비용 신장 트리 (Minimum Spanning Tree : MST) 신장 트리 중 간선의 가중치 합이 최소인 트리이다. 가중치가 존재하는 무방향 Graph에서 Spanning Tree(이하 신장 트리)를 무작위로 만들어 었을 경우 cost는 다양하게 나옵니다. 하지만 그중에서 최소 비용으로 만드는 신장 트리를 Minimum Spanning Tree(이하 최소비용 신장 트리)라고 한다 사진을 보면 Graph에서 Cost(가중치합)을 고려 안한 신장 트리를 제작을 했을 경우 Cost가 13이 나오게 됩니다. 여기서 Cost를 최소한으로 줄여본 신장 트리는 Cos.. 2024. 4. 7. 이전 1 다음 728x90
