반응형 prim2 swea 1251. [S/W 문제해결 응용] 4일차 - 하나로 Java (크루스칼) 문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 2021.12.15 - [알고리즘] - [알고리즘] 크루스칼(Kruskal)과 프림(Prim) 이번엔 최소 스패닝(신장) 트리(MST)문제이다. MST란 모든 정점을 연결하는 간선들의 가중치의 합이 최소인 트리를 말하고, 이를 구하는 알고리즘으로는 대표적으로 크루스칼(Kruskal), 프림(Prim)알고리즘이 있다. 간단하게 Prim은 정점 중심으로 동작, 크루스칼은 간선 중심으.. 2022. 2. 20. [알고리즘] 크루스칼(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 다음 반응형