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

Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish.
Reja

1. 
   Yo’naltirilmagan graflar.
   
2. 
   Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish algoritmi.
   
3. 
   Minimal narxli daraxtlar skeleti.
   

Yo’naltirilmagan graflar
Yo’naltirilmagan graf G=(V, E) – bu tugunlar va ularni birlashtirib turuvchi yoylar dan tashkil topgan tuzilma xisoblanadi. Undagi ixtiyoriy yoy teskarisi bilan teng va u yo’naltirilmagan yoy deyiladi. Agar bo’lsa, u xolda u va v tugunlar qo’shni deyiladi va e yoy esa insident deyiladi. Tugunlarning chiqish darajasi deb u bilan qo’shni tugunlar soniga aytiladi. Chiqish darajasi 0 ga teng bo’lgan tugunlar izolyasiyalangan tugun deyiladi.
E’tibor qilish kerakki, yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi. Masalan, quyidagi rasmda yo’naltirilgan G₁=(V₁, E₁) grafda V₁={ a,b,c,d}tugunlar va E₁={ (a,b), (a,c), (b,b), (b,d), (d,a)} yoylar berilgan bo’lsin. Unda G₂=(V₂, E₂)yoy ilmoq xisoblanadi va uning kirish darajasi 2 ga, chiqish darajasi xam 2 ga teng. G₂ Grafda esa e tugunning darajasi 0 ga teng va izolyasiyalangan.

1-rasm. Yo’naltirilgan G1 va yo’naltirilmagan G2 graflar.

Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish algoritmi

Yo’naltirilmagan graflarni ko’ruvdan o’tkazishda ma’lumotlarni saqlash uchun bironta konteyner yoki stekdan foydalaniladi. Konteyner yordamida ko’ruvdan o’tkazishda graflar eniga qarab ko’ruvdan o’tkaziladi. Uni algoritmini ko’rib chiqamiz. Ushbu graf berilgan bo’lsin.

1. 
   Ko’ruvdan o’tkazishni ixtiyoriy bir v tugundan boshlaymiz.
   
2. 
   Uni konteynerga tashlaymiz.
   

Queue q;
q.push(v);
3. navbat bo’shamaguncha
While(!q.empty())

1. 
   Navbatdan tugunni chiqaramiz va uni ko’ruvdan o’tkazilganligini belgilaymiz. mark(current=q.pop());
   
2. 
   Barchainsident yoylarni tekshiramiz.
   
   1. 
      Agar yoy ko’ruvdan o’tmagan u tugunga olib borsa, uni navbatga joylaymiz. q.add(u);
      
   2. 
      Aksxoldaagaryoynavbatgakiritilganyokiko’rilgan tugunga olib borsa, xech nima qilmaymiz.
      

2-rasm. Navbat yordamida grafni ko’ruvdan o’tkazish etapi.