Amaliy ish №13 Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari Minimal kenglikdagi daraxt. Kruskal algoritmi

Eng oddiy amalga oshirish
Bu kod bevosita yuqorida tavsiflangan algoritmni amalga oshiradi va O(M log N + N²) da ishlaydi. Uchlarni saralash O(M log N) operatsiyalarini talab qiladi. Uchning ma'lum bir pastki daraxtga tegishliligi oddiygina tree_id massivi yordamida saqlanadi - har bir uch uchun u tegishli bo'lgan daraxtning raqamini saqlaydi. Har bir uch uchun biz O (1) da uning uchlari turli daraxtlarga tegishli yoki yo'qligini aniqlaymiz. Nihoyat, ikkita daraxtni birlashtirish O(N) da oddiygina tree_id massivi orqali takrorlash orqali amalga oshiriladi. Jami N-1 birlashma operatsiyalari bo'lishini hisobga olsak, biz O asimptotikani olamiz (M log N + N²).
Natijaviy minimal qoldiq graf:

Bu yerga Minamal qoldiq daraxt qirralari summasi:
1+2+8+4+4+2+7+9 = 37
Cpp dagi kodi:
#include
#include
#include

using namespace std;

int main(){
int n, m;
cin >> n >> m;
vector < pair < int, pair > > g (m); // vazn:1-uch – 2-uch
int u, v, c;
for (int i = 0; i < m; i++) {
cin >> u >> v >> c;
g[i] = make_pair(c, make_pair(u, v));
}
long long cost = 0;
vector < pair > res;

sort (g.begin(), g.end());

vector tree_id (n);
for (int i=0; i tree_id[i] = i;
for (int i=0; i int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
if (tree_id[a] != tree_id[b])
{
cost += l;
res.push_back (make_pair (a, b));
int old_id = tree_id[b], new_id = tree_id[a];
for (int j=0; j if (tree_id[j] == old_id)
tree_id[j] = new_id;
}
}
cout << "Minamal qoldiq daraxt qirralari summasi: " << cost << endl;
cout << "Qolgan qirralar: " << endl;
for (int i = 0; i < res.size(); i++) {
cout << res[i].first<<" "<}
}
Natija: