grafni to’liq aylanib chiqish.bfs va dfs algoritmlari

PPTX 39 sahifa 2,4 MB Bepul yuklash

39 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 2,4 MB

Fayl turi PPTX

Sahifalar 39

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 39

grafni to’liq aylanib chiqish. bfs va dfs algoritmlari. grafni to’liq aylanib chiqish. bfs va dfs algoritmlari. ma’ruzachi: m.tojiyev 1 graflarni aylanib chiqish turlari graflar bo'yicha masalalarni hal qilish uchun bizga graflarni kesib o'tish mexanizmi kerak. grafni aylanib o'tish algoritmlari graf qidiruv algoritmlari deb ham ataladi. daraxtlarni kesib o'tish algoritmlari (inorder, preorder, postorder va level-order o'tishlari) singari, graf qidirish algoritmlarini grafdagi ba'zi manba tugunlarida siljish va qirralardan o'tish va tugunlarni belgilash orqali grafni "qidirish" deb hisoblash mumkin. graflarni kesib o'tishning ikkita algoritmni ko’rib chiqamiz. depth first search – dfs (chuqurlik bo’yicha qidirish) breadth first search –bfs (kenglik bo’yicha qidirish) 2 bfs (kenglik bo’yicha qidirish) algoritmi nima? kenglik bo’yicha qidiruv (bfs) - bu ma'lum bir tugundan (boshlang'ich tugun deb atalgan) boshlanadigan grafdagi barcha tugunlarni topadigan grafni aylanib o'tish algoritmidir. bfs boshlang'ich tugunga tashrif buyurishdan boshlanadi, so'ngra barcha qo'shni tugunlarga tashrif buyurishga o'tadi va hokazo. joriy tugunning barcha qo'shni tugunlariga tashrif buyurilganda, bfs …

2 / 39

ni kesib o'tish nima? grafni kesib o'tish - bu grafdagi cho'qqilarni aniqlash uchun keng qo'llaniladigan metodologiya. bu kengaytirilgan qidiruv algoritmi bo'lib, u tashrif buyurilgan cho'qqilar ketma-ketligini belgilash bilan birga grafni tezlik va aniqlik bilan tahlil qila oladi. ushbu jarayon cheksiz siklda qulflanib qolmaslikni, grafdagi har bir tugunni tezda aylanib chiqish imkonini beradi. 5 bfs algoritmi arxitekturasi quyidagi bosqichlarni o'z ichiga oladi: grafning dastlabki tugunini tanlash. boshlang'ich tugun joylashtirilgan navbat yaratish. tashrif buyurilgan deb boshlang'ich tugunni belgilash. navbatdan birinchi tugunni chiqarish va qo'shni tugunlar ro'yxatini olish. hali tashrif buyurmagan har bir qo'shni tugun uchun uni tashrif buyurilgan deb belgilash va uni navbatning oxiriga qo’shish kerak. navbat bo'sh qolguncha 4-5-bosqichlarni takrorlanadi. bfs algoritmi qanday ishlaydi? graflarni kesib o'tish algoritmidan daraxt tuzilishidagi har bir ko'rilmagan tugunga tashrif buyurish ya’ni tekshirish va/yoki yangilashni talab qiladi. grafni kesib o'tish ularning grafdagi tugunlarga tashrif buyurish tartibi bo'yicha tasniflanadi. bfs algoritmi operatsiyani grafdagi birinchi yoki boshlang'ich tugundan …

3 / 39

i uchun queue’ga qo’shilmaydi. a vertex’ga bog’langan ikki vertex bor – b va g. ularni queue’ga qo’shamiz va «ko’rilgan» qilib belgilaymiz. ularni qaysi tartibda qo’shishning ahamiyati yo’q. a ga bog’langan vertex’lar tekshirib bo’lingach, a vertex uchun ish yakunlanadi. queue’da birinchi b turgani uchun undan ish davom ettiriladi. b queue’dan o’chiriladi. b ning barcha bog’langan ko’rilmagan vertex’lari queue’ga qo’shiladi. b da bitta ko’rilmagan vertex – c queue’ga qo’shilgach, ko’rilgan qilib belgilanadi. b ishini tugatadi. queue’da g birinchi turgani uchun u queue’dan olinib, ish davom ettiriladi. g ning ikkita ko’rilmagan vertex’i bor: e va j. ular queue’ga qo’shiladi. g ishini tugatadi. queue’da birinchi turgan vertex – c dan ish davom ettiriladi. c da ko’rilmagan vertex yo’q. c da ish tugaydi. queue’da e birinchi turgani uchun, e dan davom ettiriladi. e’ning bitta ko’rilmagan vertex’i – k queue’ga qo’shiladi. e uchun ish tugaydi. queue’da keyingi element – j dan ish davom ettiriladi. j ning …

4 / 39

; console.write(s + " "); foreach (int i in adj[s]) { if (!visited[i]) { visited[i] = true; queue.enqueue(i); } } } }} 23 class program { static void main(string[] args) { graph g = new graph(9); // добавление ребер g.addedge(0, 1); g.addedge(0, 2); g.addedge(1, 2); g.addedge(2, 3); g.addedge(1, 5); g.addedge(1, 4); g.addedge(3, 4); g.addedge(4, 5); g.addedge(4, 8); g.addedge(5, 6); g.addedge(5, 7); g.addedge(7, 8); g.addedge(6, 7); g.addedge(6, 8); console.writeline("результат поиска в ширину начиная с вершины 0:"); g.bfs(0); } } 24 natijalar 25 vaqt murakkabligi bfs ning vaqt murakkabligi o(v+e) ga teng, bu yerda v tugunlar soni va e - qirralarning soni. buning sababi shundaki, har bir tugun va qirra aynan bir marta tashrif buyuriladi. bfs ning afzalliklari foydasiz yo'llarni cheksiz o'rganishda tiqilib qolmaydi. agar mavjud bo'lsa, u yechim topadi. agar bir nechta yechim mavjud bo'lsa, u eng qisqasini topishi mumkin. dasturlash oson. bu kam saqlashni talab qiladi. bfs kamchiliklari uning xotira …

5 / 39

orqali yo’l topishni trémaux maze exploration deb ham ataladi. labirint yechishni dasturda modellashtirish uchun labirintni graph’ga aylantiramiz. bunda labirintning yo’llari edge’lar, chorrahalar vertex’lar bo’ladi. chuqurlik bo’yicha qidirish dastlab boshlang'ich o'tish nuqtani tanlash bilan boshlanadi, bu bizning misolimizda a tugun. keyin algoritm uchta operatsiyani bajaradi: tugunga tashrif buyuradi, uni stekga so’radi va qayta ko'rib chiqishning oldini olish uchun uni belgilaydi. keyin algoritm a ga qo'shni bo'lgan, hali tashrif buyurmagan istalgan tugunga o'tadi. biz tugunlar alifbo tartibida tanlangan deb taxmin qilamiz; shuning uchun u b tugun bo'ladi. algoritm b ga tashrif buyuradi, tugunni belgilaydi va uni stekga so’radi. xo’sh qanday davom etadi ushbu jarayon? joriy cho'qqi b, shuning uchun algoritm avvalgidek ishlaydi: u ilgari tashrif buyurilmagan qo'shni tugunga o'tadi. bizning misolimizda bu tugun f. bu jarayonning qoidasini 1 – qoida sifatida belgilaymiz. 1-qoida ilgari tashrif buyurmagan qo'shni tugunga tashrif buyurish kerak va uni belgilab stekka joylashtirish kerak. 1-qoidani yana qo'llash h tugunga …

Ko'proq o'qimoqchimisiz?

Barcha 39 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"grafni to’liq aylanib chiqish.bfs va dfs algoritmlari" haqida

grafni to’liq aylanib chiqish. bfs va dfs algoritmlari. grafni to’liq aylanib chiqish. bfs va dfs algoritmlari. ma’ruzachi: m.tojiyev 1 graflarni aylanib chiqish turlari graflar bo'yicha masalalarni hal qilish uchun bizga graflarni kesib o'tish mexanizmi kerak. grafni aylanib o'tish algoritmlari graf qidiruv algoritmlari deb ham ataladi. daraxtlarni kesib o'tish algoritmlari (inorder, preorder, postorder va level-order o'tishlari) singari, graf qidirish algoritmlarini grafdagi ba'zi manba tugunlarida siljish va qirralardan o'tish va tugunlarni belgilash orqali grafni "qidirish" deb hisoblash mumkin. graflarni kesib o'tishning ikkita algoritmni ko’rib chiqamiz. depth first search – dfs (chuqurlik bo’yicha qidirish) breadth first search –bfs (kenglik bo’yicha qidirish) 2 bfs (kenglik bo’yich...

Bu fayl PPTX formatida 39 sahifadan iborat (2,4 MB). "grafni to’liq aylanib chiqish.bfs va dfs algoritmlari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: grafni to’liq aylanib chiqish.b… PPTX 39 sahifa Bepul yuklash Telegram