|
yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi
|
| bet | 2/4 | | Sana | 14.05.2024 | | Hajmi | 0,98 Mb. | | #230833 |
Bog'liq MBma`ruza1yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi. yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi. Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish algoritmi Grafni ko’rikdan o’tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni ko’rib chiqish prosedurasidir. Ikkita usuli mavjud: - Tubiga qarab(Depth-First Search – DFS)
- Eniga qarab(Breadth-First Search – BFS)
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
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());
- Акс холда агар ёй навбатга киритилган ёки кўрилган тугунга олиб борса, хеч нима қилмаймиз.
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
|
| |
