봉황대 in CS

최소 신장 트리 (Minimum Spanning Tree, MST) 최소 신장 트리는 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중, 그 가중치의 합이 최소인 트리를 말한다. * 부분 그래프(Subgraph) : 주어진 그래프에서 일부 정점과 간선만을 선택하여 구성한 그래프 더 쉽게 말하자면 가장 적은 비용으로 모든 노드를 연결한 그래프를 말하며, 이때 사이클이 발생하면 안 된다. * 정점 = 노드 * 간선 = 비용 = 가중치 (그래프에서 선에 해당하는 부분) 동일한 그래프에서 최소 신장 트리는 여러 개가 나올 수 있다. 가중치의 합이 최소이기만 하면 되기 때문이다. 최소 신장 트리를 구하기 위한 알고리즘은 2가지가 존재하며, 각각 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이다...