Samarqand davlat universiteti raqamli texnologiyalar fakulteti dasturiy injiniring yo

from pythonds.graphs import PriorityQueue, Graph, Vertex

def prim(G,start):

pq = PriorityQueue()

for v in G:

v.setDistance(sys.maxsize)

v.setPred(None)

start.setDistance(0)

pq.buildHeap([(v.getDistance(),v) for v in G])
while not pq.isEmpty():

currentVert = pq.delMin()

for nextVert in currentVert.getConnections():

newCost = currentVert.getWeight(nextVert) \

+ currentVert.getDistance()

if nextVert in pq and newCost

nextVert.setPred(currentVert)

nextVert.setDistance(newCost)

pq.decreaseKey(nextVert,newCost)

Yuqoridagi rasmlarda (10 dan 17 gacha) oddiy daraxt algoritmining misoli qanday ishlashini ko'rish mumkin. Biz A tepalikdan boshlaymiz. Boshqa barcha tepaliklar uchun masofa cheksizgacha boshlanadi. A qo'shnilarini ko'rib chiqib, biz ikkita qo'shimcha B va C tepaliklarining yo'l qiymatlarini yangilaymiz, chunki ularga A gacha bo'lgan masofa cheksizlikdan kam. Bu B va C ni ustuvor navbatning old qismiga o'tkazadi. Biz ushbu tugunlarning havolalarini avvalgisiga yangilab, ularni A ga o'rnatamiz. Shuni ta'kidlash kerakki, biz hali ham daraxtga B va C ni qo'shmadik. Tugun ustuvor navbatdan olib tashlanmaguncha uning bir qismi hisoblanmaydi.

B eng kichik masofaga ega bo'lgani uchun biz uni keyingi deb hisoblaymiz. B qo'shnilarini tekshirish D va E yo'llarni yangilash mumkinligini ko'rsatadi. Ushbu ikkala tugun masofaning yangi qiymatlarini va oldingisiga yangilangan havolalarni oladi. Keyingi tugunga ustuvorlik bilan ketma-ket o'tib, S ni topamiz, u hali ham navbatda turgan yagona qo'shni tugun F hisoblanadi. Shuning uchun biz unga masofani yangilab, navbatdagi o'rnini sozlashimiz mumkin.

Endi biz D tuguniga tutash vertikalarni tekshiramiz. E ni yangilashimiz va uning masofasini 6 dan 4 gacha qisqartirishimiz mumkinligini aniqladik. Buni amalga oshirganimizda, E ning oldingisiga havola D ga o'rnatiladi, bu tugunni bo'lishga tayyorlaydi yoyilgan daraxtga qo'shilgan (boshqa holatda bo'lsa ham).