|
Kruskal algoritmini c++ da amalga oshirish
|
| bet | 2/7 | | Sana | 28.07.2023 | | Hajmi | 0.93 Mb. | | #77545 |
Bog'liq algoritm mustaqil ish иш хақи, Mavzu Antivirus-dasturlari, 1-SINF, V sinf texnologiya va dizayn yo‘nalishi buyicha 5-sinflar uchun , Nometal materiallar, Жуфт сузлар, дарс ишланма сон, BEKLEMISHEV KLASSIFIKATSIYASIGA KO, A new generation of realistic writers, Ochiq faoliyat ishlanma 2, Zamonaviy sunKruskal algoritmini c++ da amalga oshirish
Biz tegishli ma'ruzadan barcha optimallashtirishlar bilan DSU dasturidan foydalanamiz:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include
using namespace std;
int p[100000];
int rk[100000];
void init_dsu() {
for (int i = 0; i < 100000; i++) {
p[i] = i;
rk[i] = 1;
}
}
int get_root(int v) {
if (p[v] == v) {
return v;
} else {
return p[v] = get_root(p[v]);
}
}
bool merge(int a, int b) {
int ra = get_root(a), rb = get_root(b);
if (ra == rb) {
return false;
} else {
if (rk[ra] < rk[rb]) {
p[ra] = rb;
} else if (rk[rb] < rk[ra]) {
p[rb] = ra;
} else {
p[ra] = rb;
rk[rb]++;
}
return true;
}
}
struct edge {
int a, b, len;
bool operator<(const edge& other) {
return len < other.len;
}
};
int main() {
vector<edge> edges;
sort(edges.begin(), edges.end());
int mst_weight = 0;
init_dsu();
for (edge e: edges) {
if (merge(e.a, e.b)) {
mst_weight += e.len;
}
}
cout << "Minimum spanning tree weight: " << mst_weight << endl;
}
|
Ish tezligidagi farqlar
Ikkala algoritm ham quyidagilar uchun ishlaydi O(M log N), ularning ishlash tezligida doimiy farqlar mavjud. Kruskal algoritmi siyrak grafikalarda (qirralarning soni taxminan tepaliklar soniga teng) tezroq ishlaydi va to'yingan grafikalarda (qirralarning soni tepaliklar sonining kvadratiga teng) - Prim algoritmi (qo'shni matritsadan foydalanganda).
Amalda Kruskal algoritmi ko'proq qo'llaniladi.
Kruskal algoritmi. Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan. Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi. Vazni 6 ga tеng bo’lgan to’rtta tomondan ikkitasini qoldiramiz. Natijada qaysi ikki tomonning qoldirilishiga bo?liq holda J yoki Z rasmlarda ifodalangan MOD lardan biriga ega bo’lamiz.
a) b)
v) g)
d) e)
j) z)
Quyida ushbu algoritm matnini kеltiramiz. Bunda Е bilan grafdagi tomonlar soni, N bilan tugunlar soni ifoddalangan:
edgeCount=1
while edgeCount<=Е and includedCount<=N-1 do
parent1=FindRoot(edge[edgeCount].start)
parent2=FindRoot(edge[edgeCount].end)
if parent1/parent2 then
edge[edgeCount] ni MOD ga qo’shish
includedCount= includedCount=1
Union(parent1,parent2)
Enf if
edgeCount= edgeCount+1
end while
Algoritmning asosiy sikli edgeCount o’zgaruvchisining qiymati grafdagi tomonlar soni bilan tеnglashishi yoki includedCount o’zgaruvchisining qiymati MOD ni shakllantirish uchun еtarlicha tomonlar qo’shilganini ko’rsatgunga qadar ishlaydi (N tugunli garfning MOD i N-1 ta tomonga ega bo’lishi kеrak) .
Shunday masalalar borki, ular tez algoritmli yechimga ega bo’lmagan masalalardir (NP-to’liq masalalar Shunday masalalar haqida va ularni yechish uchun tez algoritr mla (har doim ham o’rinli emas).) bilan tanishamiz.
NP-to’liq masalalarda bunday algoritmlar optimal yechimga yaqin bo’lgan natijani olish uchun ishlatilishi mumkin.
Biz xasislik strategiyasi ya’ni, masalalar yechishni juda oddiy strategiyasi haqida bilib olamiz.
|
| |
