Prim 알고리즘 - 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(mst)란 ? 그래프에 있는 모든 정점들을 가장 적은 가중치의 합으로 연결하는것을 말한다. MST의 특징 N개의 정점과 N-1개의 간선으로 이루어진 무방향 그래프 사이클을 형성하면 안된다. 대표적인 알고리즘으로 Prim 알고리즘, Kruskal 알고리즘, dijkstra알고리즘이 있다 MST는 도로건설이나 통신 등 거리나 비용을 최소로 요구하는곳에 사용됨 Prim 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택면서 MST를 만들어가는 방식 시작 정점을 기준으로 하여 인접하는 정점들 중의 최소비용의 간선이 존재하는 정점을 선택 N-1개의 간선을 가질때 까지 반복 과정 시작정점인 0번에서 가중치가 가장 작..
