“Xassis” algoritmlar. Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari

Ushbu muammoning boshqa taniqli algoritmlariga quyidagilar kiradi Kruskal algoritmi va Borovka algoritmi. Ushbu algoritmlar uzilib qolgan grafada minimal o'rmonni topadi; Aksincha, Prim algoritmining eng asosiy shakli faqat bog'langan grafikalarda minimal uzunlikdagi daraxtlarni topadi. Biroq, Primning algoritmini har biri uchun alohida ishlatish ulangan komponent grafigidan, u minimal uzunlikdagi o'rmonni topish uchun ham ishlatilishi mumkin. Ularning asimptotik jihatidan vaqtning murakkabligi, bu uchta algoritm bir xil darajada tezdir siyrak grafikalar, ammo boshqa murakkab algoritmlarga qaraganda sekinroq. Biroq, etarli darajada zich bo'lgan grafikalar uchun Prim algoritmini ishga tushirish mumkin chiziqli vaqt, boshqa algoritmlar uchun vaqt chegaralarini yig'ish yoki takomillashtirish.

• Ushbu muammoning boshqa taniqli algoritmlariga quyidagilar kiradi Kruskal algoritmi va Borovka algoritmi. Ushbu algoritmlar uzilib qolgan grafada minimal o'rmonni topadi; Aksincha, Prim algoritmining eng asosiy shakli faqat bog'langan grafikalarda minimal uzunlikdagi daraxtlarni topadi. Biroq, Primning algoritmini har biri uchun alohida ishlatish ulangan komponent grafigidan, u minimal uzunlikdagi o'rmonni topish uchun ham ishlatilishi mumkin. Ularning asimptotik jihatidan vaqtning murakkabligi, bu uchta algoritm bir xil darajada tezdir siyrak grafikalar, ammo boshqa murakkab algoritmlarga qaraganda sekinroq. Biroq, etarli darajada zich bo'lgan grafikalar uchun Prim algoritmini ishga tushirish mumkin chiziqli vaqt, boshqa algoritmlar uchun vaqt chegaralarini yig'ish yoki takomillashtirish.

Primning algoritmi A tepadan boshlanadi, Uchinchi pog'onada BD va AB qirralarning har ikkisi ham 2 vaznga ega, shuning uchun BD o'zboshimchalik bilan tanlanadi. Ushbu qadamdan so'ng, AB daraxtga qo'shilish uchun nomzod emas, chunki u allaqachon daraxtda bo'lgan ikkita tugunni bog'laydi.

• Primning algoritmi A tepadan boshlanadi, Uchinchi pog'onada BD va AB qirralarning har ikkisi ham 2 vaznga ega, shuning uchun BD o'zboshimchalik bilan tanlanadi. Ushbu qadamdan so'ng, AB daraxtga qo'shilish uchun nomzod emas, chunki u allaqachon daraxtda bo'lgan ikkita tugunni bog'laydi.