MST 썸네일형 리스트형 최소 신장 트리 신장 트리 개념 그래프 내의 모든 정점을 포함하는 트리 n개의 정점으로 이루어진 무방향 그래프에서 n-1개의 간선으로 이루어진 트리 특징 하나의 트리에는 다수의 신장트리가 존재할 수 있음 모든 정점들이 연결되어 있어야 하며, 싸이클을 포함해서는 안된다. 최소 신장 트리 개념 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 특징 가중치의 합이 최소여야 함 n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용해야함 사이클이 포함되면 안됨 활용 그래프에서 최소 비용을 구할때 활용 ※구현 방법 Prim 알고리즘 개념 하나의 정점에서 출발하여 연결된 간선들 중 하나씩 선택하면서 MST를 만들어나가는 방식 시간 복잡도 O(n^2) 특징 정점 선택 기반 이전의 ms.. 더보기 이전 1 다음
