최소 스패닝 트리 (네트워크 연결) 힙을 이용한 prim 알고리즘으로 풀었다. 1. heap에 시작 정점 1과 가중치 0 [[0,1]] 삽입 2. heap에서 정점과 가중치를 꺼냄 3. 꺼낸 정점이 방문하지 않은 정점이라면 결과에 가중치를 더함 4. 그 정점에서 다른 정점으로 향하는 정보 i를 힙에 삽입 5. 위의 과정을 반복하다가 count가 정점의 수 V가 되면 종료 알고리즘 문제/트리 2022.03.07
최소 스패닝 트리 (MST, Minimum Spanning Tree) Spanning Tree 특징 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. V개의 정점을 (V-1)개의 간선으로 연결되어야 한다. MST(Minimum Spanning Tree) Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 1. Kruskal 알고리즘 2. Prim 알고리즘 시작 정점에서 부터 출발하여 스패닝 트리 집합을 단계적으로 확장 Prim 알고리즘의 동작 과정 시작 정점을 힙에 저장 방문하지 않은 정점중에서 가중치가 가장 낮은 정점을 선택 위 과정을 트리가 (V-1)개의 간선을 가질 때 까지 반복 백준 1922 알고리즘 2022.03.03
