| v | v | v | G----14|---- H----4----| | | | 2| | 10| 9| | | | | | Q----------P----------R S - Nomi bilan xususiyatlari:
Tugalgan tarmoqlar : A, B, C, D, G, F, E, H, R, Q, P, S. - Ulcham muddati :
- A - B : 7
- B - E : 6
- E - R : 4
- R - S : 2
- S - P : 9
- P - Q : 10
- Q - G : 5
- G - D : 9
- D - C : 8
- C - A : 15
- C - G : 14
- B - F : 10
- F - H : 13
- H - D : 6
Kruskal algoritmi quyidagi qadamdan iborat: - Kruskal algoritmi quyidagi qadamdan iborat:
- 1. Tarmoqni qurilish
- 2. Qatnashuvchilar keldi chiqish tartibi boyicha saralash
- 3. Eng arzon sinov tarmoqini qo'lga kiritish
- 4. Keyingi eng arzon tarmoqni qabul qilish, agar bu tarmoq MST ni to'ldirishdan parizod bo'lsa
- 5. Eng arzon tarmoqni MST ga qo'shish
- 6. Tarmoqlar to'g'ris
- Prima algoritmi bu yilda Kompyuter fanlari, Primlar (shuningdek, nomi bilan tanilgan Jarniknikidir) algoritm a ochko'zlik algoritmi topadigan a minimal daraxt daraxti a vaznli yo'naltirilmagan grafik. Buning ma'nosi uning qirralar bu shakllanadigan a daraxt har birini o'z ichiga oladi tepalik, bu erda hamma og'irligi qirralar daraxtda minimallashtiriladi. Algoritm ushbu daraxtni har bir qadamda o'zboshimchalik bilan boshlanadigan tepalikdan boshlab bitta tepalikni qurish orqali ishlaydi, bu daraxtdan boshqa tepaga iloji boricha eng arzon ulanishni qo'shadi.
- Algoritm 1930 yilda ishlab chiqilgan Chex matematik Voytech Jarnik va keyinchalik qayta kashf etilgan va qayta nashr etilgan kompyuter olimlari Robert C. Prim 1957 yilda va Edsger V. Dijkstra 1959 yilda. Shuning uchun, ba'zida uni Jarnik algoritmi, Prim-Jarnik algoritmi, Prim –Daykstra algoritmi yoki DJP algoritmi.
Do'stlaringiz bilan baham: |
