60-rasm. Kruskal algoritmining bajarilish ketma-ketligi Kruskal algoritmini realizatsiya qilish (C++ kodi) int n, m; cin >> n >> m; vector > edges(m, vector(3)); for (int i = 0; i < m; ++i) cin >> edges[i][1] >> edges[i][2] >> edges[i][0]; sort(edges.begin(), edges.end()); vector comp(n); for (int i = 0; i < n; ++i) comp[i] = i; int ans = 0; for (auto & edge: edges) { int weight = edge[0]; int start = edge[1]; int end = edge[2]; if (comp[start] != comp[end]) { ans += weight; int a = comp[start]; int b = comp[end]; for (int i = 0; i < n; ++i) if (comp[i] == b)
178
comp[i] = a; } } 15.2. Prima algoritmi Prima algoritmi quyidagi tartibda ishlaydi
Dastlabki berilgan graf
1-bosqich. Uchni tanlash
2-bosqich. Ushbu uchdan eng qisqa
qirrani tanlash va uni qo'shish
3-bosqich. Grafdan hali tanlanmagan
eng yaqin uchni tanlash
4-bosqich. Grafda hali
topilmagan eng yaqin uchni
tanlang, agar bir nechta
variant, tasodifiy birini tanlash
179
Keyingi bosqichlar. Yuqoridagi ishlarni daraxt hosil boʻlguncha
takrorlash
Prima algoritmining C++ kodi Quyidagi dastur Primaning algoritmini C ++ da amalga oshiradi.
Grafni ko'rsatish uchun qo'shnilik matritsa ishlatilgan bo'lsa-da, ushbu
algoritm samaradorligini oshirish uchun qo'shnilik ro'yxati yordamida
ham amalga oshirilishi mumkin.
