학교/자료구조
2023. 6. 6.
[자료구조] 6장 실습 kruskal, prim, sollin
최소비용 신장트리 알고리즘 minheap : 노드 키 값 priority queue 사용 priority_queue PQ; 최소비용 신장트리이므로 minheap, PQ의 top()이 최소비용임 알고리즘 흐름 정리 kruskal은 전체 트리 중 가장 최소 비용의 간선들만 차례로 택한다 prim은 가장 최소 비용 간선 택, 포함된 정점의 edge들 중 최소 비용 edge 택 sollin은 모든 정점들의 최소 비용 간선 택 => 연결 반복 kruskal 정의 한 번에 한 간선씩 추가 T에 포함될 간선은 가장 적은 비용 순으로 택 사이클 형성하는 간선은 제외 n-1개 간선 적용 void kruskal() { Sets sets(NNODES); int nedges = 0; while ((ned..