Vaqt murakkabligi
O(V²)
Prim algoritmi vaznli, bog‘langan va yo‘naltirilmagan graf uchun minimal qamrovchi daraxtni (MST) topadi. MST barcha uchlarni qirralarning umumiy vazni eng kichik bo‘lgan holda bog‘laydi.
Qanday ishlaydi:
1. Istalgan uchni boshlang‘ich daraxt sifatida tanlash
2. Daraxtni hali unga kirmagan uch bilan bog‘laydigan eng kichik vaznli qirrani topish
3. Ushbu qirra va uchni daraxtga qo‘shish
4. Barcha uchlar daraxtga kiritilguncha takrorlash
Vaqt murakkabligi:
Qo‘shnichilik matritsasi bilan: O(V²)
Ikkilik uyum (binary heap) bilan: O(E log V)
Xotira murakkabligi: O(V)
Qo‘llanilishi:
- Tarmoqlarni loyihalash (eng kam xarajatli kabel ulanishi)
- NP-qiyin masalalar uchun yaqinlashtirish algoritmlari
- Klaster tahlili
- Tasvirlarni segmentatsiyalash
Prim algoritmi — daraxtni kengaytirish uchun har safar eng arzon qirrani tanlaydigan ochko‘z algoritm. Uni barcha qirralarni umumiy tartibda saralaydigan Kruskal algoritmi bilan taqqoslash mumkin.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Prim algoritmi nima?
- Prim algoritmi vaznli, bog‘langan va yo‘naltirilmagan graf uchun minimal qamrovchi daraxtni (MST) topadi. MST barcha uchlarni qirralarning umumiy vazni eng kichik bo‘lgan holda bog‘laydi.
- Prim algoritmi murakkabligi qanday?
- Vaqt (o'rtacha): O(V²) · Xotira: O(V)
- Ushbu Prim algoritmi vizualizatori kimlar uchun?
- Prim algoritmi vizualizatsiyasi "Graflar" kategoriyasida yuqori darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Prim algoritmi ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Graflar) quyidagilarni ko'rishingiz mumkin: Breadth-First Search, Depth-First Search, Dijkstra's Algorithm. Har biri interaktiv vizualizatsiyaga ega.