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 newCostnextVert.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).