Minimum spanning tree’ni topish uchun Prim algoritmi

Minimum spanning treeni topishning yana bir klassik algoritmlaridan biri – Prim algoritmi ishlash tartibi quyidagicha:

1. 0-vertex’dan ishni boshlaydi.
2. Vertex’ning edge’larini weight bo’yicha saralangan holida priority queue‘ga qo’shadi. Bunda ikki vertex’i allaqachon ko’rilgan edge’larni tushirib qoldiradi.
3. Priority queue’dan minimum edge’dagi vertex’ni olib ishni davom ettiradi. Demak tree ish yakunigacha connected holda qoladi.
4. MST da edge’lar soni V – 1 bo’lganda ishni yakunlaydi. V – graph’dagi vertex’lar soni.

Kodda ifodalash

Prim algoritmidagi o’ylantiradigan vazifa – priority queue‘ga qanday qilib edge’larni qo’shish va kerakmas edge’larni queue’dan o’chirish bo’lishi mumkin. Masalan yuqoridagi misolda, MSTga 2-0 edge qo’shilganidan keyin priority queue’da bo’lgan 1-2 va 2-7 o’chiriladi. Sababi bu edge’larning ikki vertex’i ham ko’rib bo’lindi. Biz o’chirishni alohida ko’rmasdan, umumiy iteratsiyada tushirib qoldiramiz. Aniqrog’i agar edge’ning ikki vertex’i allaqachon ko’rilgan bo’lsa, continue qilib, keyingi siklga o’tib ketamiz.

Kod Githubda: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/graphs/minimum-spanning-tree/prim-mst.js

* * *

Mavzu bo’yicha savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozishingiz yoki kodda Reference in new issue ni bosib, qoldirishingiz mumkin.