-misol. DFS algoritmining ishlashi

105 
2-uchda ko'rilmagan qo'shni 4-uch bor, shuning uchun biz uni 
to'plamning yuqori qismiga qo'shamiz va tashrif buyuramiz. 
 
 
Oxirgi 3-bandga tashrif buyurganimizdan so'ng, uning ko'zga 
ko'rinmas qo'shni uchlar yo'q. Bu grafni birinchi chuqurlik birinchi 
o'tishini yakunlaydi. 
 
Mavzu yuzasidan savollar:
1.
Graflarda oʻtish algoritmlari qanday masala hisoblanadi? 
2.
BFS algoritmining ishlash prinsipi qanday? 
3.
DFS algoritmining ishlash prinsipi qanday? 

106 
4.
Graflarda yana qanday oʻtish algoritmlari mavjud? 
5.
Yuqorida keltirilgan algoritmlarning murakkabligini baholang 

107 
8-§. Daraxtlar grafning xususiy holati sifatida 
Daraxt
- bu bogʻlangan asiklik graf, ya‘ni sikllar yoʻq va uchlar 
juftligi orasida bitta yoʻl bor (29-rasm). Kirishning nol darajasiga ega 
boʻlgan uch 
daraxtning
ildizi, chiqish nol darajaga ega tugunlar esa 
barglar
deb nomlanadi. 
Ulanish har qanday uchlar juftligi oʻrtasida marshrut mavjudligini 
anglatadi, aylanuvchanlik sikllar yoʻqligini anglatadi. Demak, xususan, 
shundan kelib chiqadiki, daraxtdagi qirralarning soni uchlar sonidan 
bitta kamroq va har qanday uchlar juftlari orasida bitta va faqat bitta yoʻl 
bor. 

Download 4,61 Mb.