greedy1 프림 알고리즘 Prim's Algorithm 일정 시간 복잡도 MST(minimum spanning tree)구하는 알고리즘 정점 선택 기반으로 가중치 제일 낮은 방향으로 이전 단계의 신장트리를 확장해나간다. 트리가 N-1개의 간선을 가질 때까지 반복한다. 의사 코드를 보면 다음과 같다. void prim(int n, const numberW[][], set_of_edges& F) //정점 개수, 간선 정보, 방문 간선 { index i, vnear; number min; edge e; index nearest[2..n]; //해당 인덱스의 정점에서 가장 가까운 정점 정보 number distance[2..n]; //현재 방문한 정점에서 해당 인덱스의 정점까지 거리(최단) F = ∅; for(i = 2; i 2021. 6. 8. 이전 1 다음