목록프림 (1)

algoqna

최소 비용 신장트리(MST : Kruskal / Prim)

* 최소비용 신장트리: 간선의 가중치가 가장 작은 것부터 처리하여 정점들을 모두 연결, 최소의 비용을 가지는 트리 생성 KRUSKAL 1) 모든 간선을 가중치에 따라 오름차순으로 정렬 ● KRUSKAL 알고리즘에서 가장 오버헤드가 많이 발생하는 부분 ● 간선의 개수에 따라 KRUSKAL을 사용할 지 말지를 고민해야함 2) 가중치가 가장 낮은 간선부터 선택하여 트리를 증가 ●이 때 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 ● if Union(a,b) cnt++; // cnt는 정점의 개수 -1개까지. ● Union이 불가할 때는 사이클이 생길 때임. 하여 유니온만으로 확인해도 무방하다 3) N-1개의 간선이 선택될 때까지 2를 반복 ● 간선이 선택됐다 == 정점 연결했다. ● 사용한 간선이 V-..
프로그래밍/알고리즘 개념 2023. 3. 7. 20:57
이전 Prev 1 Next 다음