프림

최소 신장 트리(Minimum Spanning Tree, MST)

신장 트리(Spanning Tree) 신장 트리란, 사이클을 형성하지 않는 그래프를 말한다. 나는 부모님의 자식이 될 수 있지만 내 형제자매의 자식은 될 수 없는 것처럼, 사이클이 없다는 것은 부모-자식 관계만 형성된다는 것이고 따라서 신장 트리는 트리의 형태를 가지고 있다. // 신장 트리의 특징 1. 그래프의 모든 정점이 간선에 의해 하나로 연결됨 2. 그래프 내에서 사이클 형성 X (첫 번째 그래프도 오른쪽으로 90도 회전시키면 트리처럼 보임) 최소 신장 트리(Minimum Spanning Tree) 가중치가 있는 그래프에서도 신장 트리를 구성할 수 있는데, 신장 트리의 모든 간선의 가중치 합이 최소인 그래프를 최소 비용 신장 트리(Minimum Cost Spanning Tree) 또는 최소 신장 ..