O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

Stek yordamida grafni ko’ruvdan o’tkazish algoritmi.
Oraliq qiymatlarni ushlab turish uchun stekdan foydalanilsa, graflarni tubiga qarab ko’ruvdan o’tkazish mumkin. Yuqorida keltirilgan graf va stek berilgan bo’lsin.

1. 
   Bironta tugundan boshlaymiz. Tugunni stekka tashlaymiz.
   
2. 
   Stek bo’shamaguncha
   
   1. 
      undagi tugunni olib ko’ruvdan o’tkazilganligini belgilaymiz
      
   2. 
      u bilan qo’shni tugunlarni o’qib olib tekshiramiz, agar ular ko’ruvdan utmagan bo’lsa va stekda bo’lmasa, ularni stekka tashlaymiz, aks xolda xech nima qilinmaydi.
      

Agar rasmdagi grafni navbat bilan ko’ruvdan o’tkazsak, tugunlar 1 2 4 5 3 6 7 8 ketma ketlikda, stek bilan esa 1 5 8 7 6 4 3 2 ketma ketlikda ko’rikdan o’tkaziladi.
Minimal narxli daraxtlar skeleti
Minimal narxli skeletni topish masalasi ko’pincha quyidagicha xolatlarda uchraydi: masalan, n ta shaxar mavjud va ular orasiga yo’llarni shunaqa qurish kerakki, istalgan shaxardan ixtiyoriy boshqasiga bevosita yoki bilvosita borish mumkin bo’lsin va ular orasiga yo’l qurish sarf xarajatlari ma’lum bo’lsin. Yo’llarni qurishni shunday rejalashtirish kerakki, natijada sarf xarajat minimal bo’lsin.

3-rasm. Vaznga ega bo’lgan yo’naltirilmagan graf.
Bu masala graflar nazariyasida minimal narxli daraxt skeleti (ostovnoye derevo) deb nomlanadi.
Ushbu masalani yechishning bir qator algoritmlari mavjud:

1. 
   Primo algoritmi
   
2. 
   Kraskala (Kruskala) algoritmi
   
3. 
   Boruvka algoritmi
   

Primo algoritmi
Ushbu algoritm dastlab 1930 yilda chesh matematigi Voysex Yarnik tomonidan taklif etilgan. Keyin Robert Primo tomonidan 1957 yilda qayta ko’rib chiqilgan va ulardan tashqari E. Deykstratomonidan 1959 yilda ishlab chiqilgan.
Algoritm kirishiga yo’naltirilmagan og’irlikka ega bo’lgan graf uzatiladi.

1. 
   Boshida istalgan tugun olinadi va unga tegishli bo’lgan eng kam vaznga ega insident yoy topiladi. Topilgan yoy va unga tegishli tugunlar daraxtni shakllantira boshlaydi.
   
2. 
   Keyin bir uchi bilan daraxtga tegishli bo’lgan tugunlariga tutashgan va ikkinchi uchi esa tutashmagan boshqa yoylar xam tekshiriladi. Ulardan og’irligi kami tanlanadi.
   
3. 
   Xar bir qadamdagi yoy daraxtga qo’shilib boraveradi. Daraxtning balandligi xam 1 taga oshib boraveradi. Grafning barcha tugunlari ko’rib chiqilmaguncha algoritm davom etaveradi.
   

Algoritm natijasi bo’lib minimal narxli daraxt skeleti xisoblanadi. E’tibor qaratish lozimki, minimal narxli daraxtlarni xosil qilishda xalqa paydo bo’lishiga yo’l qo’ymaslik kerak.
Misol keltiramiz.

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.

Nazoratsavollar

1. 
   Graflarnima?
   
2. 
   Minimal narxlidaraxtlarnima?
   
3. 
   U qaerlardavanimamaqsaddaishlatiladi?
   
4. 
   Minimal narxlidaraxtniqurishniqandayalgoritmlarinibilasiz?
   

Adabiyotlar.

4. 
   AdamDrozdek. Data structure and algorithms in C++. Fourthedition. 2013. Chapter 8.