목록Prim (1)

코딩 일지

[알고리즘] 최소 신장 트리

신장 트리신장 트리(Spanning Tree)란, 그래프의 최소 연결 부분 그래프이다.N개의 정점을 가지는 그래프의 최소 간선 수는 (N-1)개이고, (N-1)개의 간선으로 연결되어 있으면 트리의 형태가 된다.신장 트리는 사이클을 포함해서는 안되며, 모든 정점들이 연결되어 있어야 한다.따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결해야 한다.최소 신장 트리최소 신장 트리(MST, Minimum Spanning Tree)란, 최소 비용의 신장 트리를 선택하는 알고리즘이다.MST의 특징은 다음과 같다.간선의 가중치의 합이 최소여야 한다.n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.사이클이 포함되어선느 안된다.MST를 구현하기 위한 방법으..
자료구조 & 알고리즘 2024. 6. 11. 19:04
이전 Prev 1 Next 다음