Mavzu: Kruskal algoritmi. Prima algoritmi. XoDеykstra-Prim algoritmi


Download 19.1 Kb.
bet3/3
Sana24.10.2023
Hajmi19.1 Kb.
#1719093
1   2   3
Bog'liq
DnguiGddzJm8inFl86We3Lk0M duF6jR

Prima algartmi
Prim algoritmi - bu grafikni kirish sifatida qabul qiladigan va har bir cho'qqini o'z ichiga olgan daraxtni tashkil etuvchi, shuningdek, grafikdan hosil bo'lishi mumkin bo'lgan barcha daraxtlar orasidagi minimal og'irliklar yig'indisiga ega bo'lgan ushbu grafik qirralarining kichik to'plamini topadigan minimal kenglikdagi daraxt algoritmidir. .

Prim algoritmi qanday ishlaydi
U global optimalni topish umidida mahalliy optimalni topadigan "ochko'z" algoritmlar deb ataladigan algoritmlar sinfiga kiradi.

Biz bir cho'qqidan boshlaymiz va maqsadimizga erishgunimizcha eng kam og'irlikdagi qirralarni qo'shishda davom etamiz.

Prim algoritmini amalga oshirish bosqichlari quyidagilardan iborat:

Ixtiyoriy cho'qqi bilan minimal kenglikdagi daraxtni ishga tushiring.
Daraxtni yangi uchlari bilan bog'laydigan barcha qirralarni toping, minimalni toping va uni daraxtga qo'shing.
Minimal kenglikdagi daraxtni olmaguningizcha 2-bosqichni takrorlashni davom eting.
Download 19.1 Kb.

Do'stlaringiz bilan baham:
1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling