최소신장트리1 [자료구조] 신장 트리, 최소 비용 신장 트리 신장 트리 (Spanning Tree) 신장(Spanning) : 모든 노드를 포함한다는 의미 트리의 일종이기 때문에 cycle이 없어야 한다. 기존 그래프가 가진 모든 노드를 순환 없이 서로 연결시킨 트리 트리 간선 : 신장 트리에 포함된 간선 비트리 간선: 신장 트리에 포함되지 않은 간선 최소 비용 신장 트리 (Minimum Cost Spanning Tree) 무향 가중 그래프의 신장 트리 중에서 가중치의 합이 최소인 신장 트리 최소 신장 트리 구하는 알고리즘 : Prim(프림), Kruskal(크루스칼) 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타.. 2020. 9. 15. 이전 1 다음
