Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. Eshonqulov

Download 4,61 Mb. Pdf ko'rish
bet	97/111
Sana	18.05.2024
Hajmi	4,61 Mb.
	#241929

1 ... 93 94 95 96 97 98 99 100 ... 111

Bog'liq
ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI

cin >> edges[i][1] >> edges[i][2] >> edges[i][0]; sort(edges.begin(), edges.end()); vector comp(n); for (int i = 0; i
int end = edge[2]; if (comp[start] != comp[end]) { ans += weight; int a = comp[start]; int b = comp[end];
Prima algoritmining C++ kodi

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.

Download 4,61 Mb.

1 ... 93 94 95 96 97 98 99 100 ... 111

Download 4,61 Mb.

Pdf ko'rish