Maqsad: Talabalar graf uchun minimal narxli daraxtlar skeletini qurish algoritmini o’rganishi, Kruskal va Primo algoritmlarini bilan ishlashni o‘rganishi

Labotoriya topshirig‘i sharti. Quyida tasvirlangan graf uchun minimal narxli daraxt skeletini qurish usullaridan Primo usuli yordamida yechilsin va dasturini tuzilsin.

Prim algoritmini amalga oshirish bosqichlari quyidagicha:

1. 
   Minimal uzunlikdagi daraxtni tasodifiy tanlangan tugun bilan boshlang.
   
2. 
   Daraxtni yangi tugunlar bilan bog'laydigan barcha qirralarni toping, minimalini toping va daraxtga qo'shing
   
3. 
   Minimal daraxt daraxti olinmaguncha, 2-bosqichni takrorlang
   

tasvir	U tanlangan tugunlar to’plami	(u,v)yoylar	v\u tanlanmagan tugunlar	izox
	{}		{A,B,C,D,E,F,G}	Dastlab daraxt tugunlar to’plami bo’sh
	{D}	(D,A) = 5 V (D,B) = 9 (D,E) = 15 (D,F) = 6	{A,B,C,E,F,G}	Ilk tugun sifatida Dolindi. Unga tegishli yoylar A,B,E,F tugunlarga olib boradi. Ularning minimal yoyligini tanlaymiz. ya’ni A
	{A,D}	(D,B) = 9 (D,E) = 15 (D,F) = 6 V (A,B) = 7	{B,C,E,F,G}
	{A,D,F}	(D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11	{B,C,E,G}
	{A,B,D,F}	(B,C) = 8 (B,E) = 7 V (D,B) = 9 sikl (D,E) = 15 (F,E) = 8 (F,G) = 11	{C,E,G}	(D,B)yoy tanlansa xalqa xosil bo’ladi. Shuning uchun uni tanlay olmaymiz.
	{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 sikl (D,E) = 15 sikl (E,C) = 5 V (E,G) = 9 (F,E) = 8 sikl (F,G) = 11	{C,G}
	{A,B,C,D,E,F}	(B,C) = 8 sikl (D,B) = 9 sikl (D,E) = 15 sikl (E,G) = 9 V (F,E) = 8 sikl (F,G) = 11	{G}
	{A,B,C,D,E,F,G}	(B,C) = 8 sikl (D,B) = 9 sikl (D,E) = 15 sikl (F,E) = 8 sikl (F,G) = 11 sikl	{}	Grafdagi barcha tugunlar tekshirib bo’ldi.