11-маъруза Йўналтирил маган графлар

Yo’naltirilmagan graflarni ko’ruvdan o’tkazishda ma’lumotlarni saqlash uchun bironta konteyner, navbat yoki stekdan foydalaniladi.

Navbat yordamida ko’ruvdan o’tkazishda graflar eniga qarab ko’ruvdan o’tkaziladi
1
2
3
4
6
7
5
8

• 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())

• Navbatdan tugunni chiqaramiz va uni ko’ruvdan o’tkazilganligini belgilaymiz. mark(current=q.pop());

• Barcha insident yoylarni tekshiramiz

• Agar yoy ko’ruvdan o’tmagan u tugunga olib borsa, uni navbatga joylaymiz. q.add(u);

• Акс холда агар ёй навбатга киритилган ёки кўрилган тугунга олиб борса, хеч нима қилмаймиз.

Graf:
1
2
4
5
7
8
6
3
Grafni eniga qarab ko’rishda navbat ishlatilishi
Agar oraliq tuzilma sifatida navbat qo’llanilsa, grafni eniga qarab ko’riladi.
1
2
3
4
6
7
5
8
Graf :
1
Eniga qarab qo’ruv daraxtini yaratsa xam bo’ladi, agar xar bir to’g’ri yoylarni belgilab olinsa.
1
2
3
4
5
6
7
8
1
Navbat:
1
2
1
1
4
5
5
2
3
4
5
6
7
8
4
2
3
5
7
6
8
Tubiga qarab ko’rishda stek qo’llanilishi
Agar oraliq tuzilma sifatida stek qo’llanilsa, grafni tubiga qarab ko’riladi.
1
2
3
4
6
7
5
8
Graf :
1
5
8
7
6
4
3
2
Tubiga qarab qo’ruv daraxtini yaratsa xam bo’ladi, agar xar bir to’g’ri va teskari yoylarni belgilab olinsa.
1
2
3
4
5
6
7
8
1
1
1
5
5
7
6
4
4
3
1
Stek :
2
3
4
5
6
7
8