Prim 썸네일형 리스트형 프림 알고리즘 (Prim's Algorithm) Minimum Spanning Tree 문제를 해결하기 위해서 보통 두 가지 종류의 알고리즘 중 하나를 선택하여 사용한다. 1. 프림 알고리즘 (Prim's Algorithm) 2. 크루스칼 알고리즘 (Kruskal's Algorithm) 이 두 가지 알고리즘 모두 MST 문제에서 최적의 값을 도출할 수 있음이 이미 증명되어 있다. 이번에는 프림 알고리즘에 대하여 알아보도록 하겠다. 프림 알고리즘의 핵심은, 현재 우리가 가지고 있는 MST와 Edge 하나로 직접적으로 연결된 Vertex 가운데 Weight가 가장 작은 것을 추가한다는 것이다. 모든 Edge를 확인했는데 V-1개의 Edge가 선택되지 않은 경우가 있다면 그래프가 Disconnected 되어있다는 뜻이다. 이미 MST에 포함된 Vertex에.. 더보기 이전 1 다음
