grafda o`tish eni bo`yicha qidiruv- bfs algoritmi

DOC 10 sahifa 838,0 KB Bepul yuklash

10 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 838,0 KB

Fayl turi DOC

Sahifalar 10

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 10

2-laboratoriya ishi. grafda o`tish eni bo`yicha qidiruv- bfs algoritmi. grafda o`tish bo`yi bo`yicha qidiruv- dfs algoritmi. topologik saralash. grafda o`tish eni bo`yicha qidiruv- bfs algoritmi. kenglik bo’yicha o’tish. ta'rif o'tish - bu grafik uchlariga ma'lum tartibda ketma-ket borish (qayta ishlash). tez-tez ishlatib turiladigan ikkita yechimdan biri bu kenglik-birinchi o'tish yoki bfs (breadth-first search, kenglik bo’yicha izlash). bfsning mohiyati judayam sodda. o'tish ma'lum bir uchga tashrif buyurishdan boshlanadi (ko'pincha butun grafni bosib o'tish uchun mustaqil shox tanlanadi). keyin algoritm ushbu uchning qo'shnilariga tashrif buyuradi. ularning keyin - qo'shnilarning qo'shnilariga va hokazo tartibda amalga oshiriladi. rasmiy ravishda, boshlang'ich uchdan to -uchgacha raqamlangan (qirralarning eng qisqa yo'lining uzunligi) bo'lsin. bfs uchlarga ko'tarilish tartibida : eng kamida eng uzoqgacha tashrif buyuradi. o’tish uchun uchlar navbati saqlanib qoladi. keyingi uchga o’tganida, hali yurib o’tilmagan va hali navbatda bo'lmagan barcha qo'shnilari navbatga qo'shiladi. tepalikka allaqachon tashrif buyurilganligini tekshirish uchun bir qator yorliqlardan foydalaniladi. dastlab, o’tadigan uchdan …

2 / 10

an oldin k masofadagi barcha uchlar belgilanadi. algoritm ham yoʻnaltirilgan, ham yoʻnaltirilmagan graflar uchun ishlaydi. algoritm gʻoyasi: birinchisiga tutash boʻlgan barcha uchlar ochiladi, ya’ni ular roʻyxatga joylashtiriladi va bitta belgini oladi. shundan soʻng, dastlabki uch toʻliq qayta ishlanadi va 2 bilan belgilanadi. roʻyxatning birinchi yuqori qismi keyingi uchga aylanadi. amaldagi bilan qoʻshni boʻlgan avval belgilanmagan barcha uchning roʻyxatning oxiriga qoʻshiladi (ochiladi). joriy uch roʻyxatdan oʻchirilib, 2 raqami bilan belgilanadi. jarayon uchlar roʻyxati boʻsh boʻlguncha davom etadi. ma’lumotlar roʻyxatining ushbu koʻrinishi navbat deyiladi. quyidagi misolni koʻrib chiqamiz (27-rasm). 27-a) rasmda grafning dastlabki koʻrinishi berilgan. 27-b) rasmda, uchlar yonida, graf uchlarini koʻrish tartibi qavsda koʻrsatilgan. breadth first search (bfs) daraxtini hosil qiladigan qirralar qalin rangda berilgan. a) b) 27-rasm. bfs algoritmi jarayonida graf uchlarini koʻrish bfs algoritmi. tasvirdan koʻrinib turibdiki, algoritmning oʻzi juda ahamiyatsiz. tashrif uchun uchlar navbati saqlanib qoladi. keyingi uchga tashrif buyurganida, hali tashrif buyurmagan va hali navbatda boʻlmagan barcha …

3 / 10

diruv (bfs)-bu graflar bilan ishlashning ko'plab muhim algoritmlari uchun asos bo'lgan, eng oddiy grafni o'tish algoritmlaridan biri. keling, "eni bo’yicha qidirish" algoritmi qanday ishlashini misol bilan ko'rib chiqaylik. biz 5 ta uchga ega bo'lgan yo'naltirilmagan grafdan foydalanamiz. biz 0 uchdan boshlaymiz, bfs algoritmi uni tashrif buyurilganlar ro'yxatiga qo'yib, uning yonidagi barcha uchlarni stekga qo'yishdan boshlanadi. keyinchalik, biz navbatning old qismidagi elementga tashrif buyuramiz, ya'ni 1 va uning yonidagi uchlarga o'tamiz. 0 tashrif buyurilgani uchun biz uning o'rniga 2 ga tashrif buyuramiz. 2-uchda ko'rilmagan qo'shni 4-uch bor, shuning uchun biz uni navbatning orqa qismiga qo'shamiz va navbatning oldida joylashgan 3 -ga tashrif buyuramiz. navbatda faqat 4-uch qoladi, chunki qo'shni yagona 3-uch 3, ya'ni 0 ga tashrif buyurilgan. biz unga tashrif buyuramiz. kenglik bo'yicha birinchi qidiruv (dfs – depth first search)- bu grafni kesib o'tish usullaridan biri. nomidan ko'rinib turibdiki, birinchi qidiruv strategiyasi grafda iloji boricha chuqurroq bo'lishi kerak. qidiruv algoritmi rekursiv …

4 / 10

chiga oladi. keyingi rivojlanishning mumkin emasligi shundan iboratki, keyingi qadam harakatlanishning bir nechta variantiga ega boʻlgan (ulardan biri toʻliq oʻrganib chiqilgan), ilgari tashrif buyurgan uch oxirgisiga oʻtish boʻladi. algoritm qanday ishlashini aniq bir misol yordamida koʻrib chiqamiz. quyidagi yoʻnaltirilmagan bogʻlangan grafda jami 5 ta uch mavjud. avval siz boshlangʻich uchni tanlashingiz kerak. qaysi uch tanlangan boʻlsa ham, har qanday holatda ham graf toʻliq oʻrganib chiqiladi, chunki yuqorida aytib oʻtilganidek, bu bitta yoʻnaltirilmagan bogʻlangan graf. oʻtish 1 tugundan boshlasin, u holda qarab chiqilgan tugunlar ketma-ketligi tartibi quyidagicha boʻladi: 1 2 3 5 4. agar ijro, masalan, 3 tugundan boshlangan boʻlsa, u holda oʻtish tartibi boshqacha boʻladi: 3 2 1 5 4. 28-rasm. bfs algoritmi jarayonida graf uchlarini koʻrish dfs algoritmi rekursiyaga asoslangan, ya’ni oʻtish funksiyasi oʻzini bajarilayotganda chaqiradi, bu esa kodni umuman ixcham qiladi. algoritmning psevdokodi quyidagicha dfs funksiya sarlavhasi (st) chiqish (st) visited[st] ← tashrif buyurgan; r = 1 uchun …

5 / 10

sol bilan qanday ishlashini ko'rib chiqaylik. biz 5 ta uchga ega bo'lgan yo'naltirilmagan grafdan foydalanmoqdamiz. biz 0 uchdan boshlaymiz, dfs algoritmi uni tashrif buyurilgan ro'yxatga qo'yishdan va barcha qo'shni uchlarni stekka joylashtirishdan boshlanadi. keyin biz 1-uchning yuqori qismidagi elementga tashrif buyuramiz va qo'shni uchlarga o'tamiz. biz allaqachon 0 ga tashrif buyurganimiz uchun, uning o'rniga 2 ga tashrif buyuramiz. 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.

Ko'proq o'qimoqchimisiz?

Barcha 10 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"grafda o`tish eni bo`yicha qidiruv- bfs algoritmi" haqida

2-laboratoriya ishi. grafda o`tish eni bo`yicha qidiruv- bfs algoritmi. grafda o`tish bo`yi bo`yicha qidiruv- dfs algoritmi. topologik saralash. grafda o`tish eni bo`yicha qidiruv- bfs algoritmi. kenglik bo’yicha o’tish. ta'rif o'tish - bu grafik uchlariga ma'lum tartibda ketma-ket borish (qayta ishlash). tez-tez ishlatib turiladigan ikkita yechimdan biri bu kenglik-birinchi o'tish yoki bfs (breadth-first search, kenglik bo’yicha izlash). bfsning mohiyati judayam sodda. o'tish ma'lum bir uchga tashrif buyurishdan boshlanadi (ko'pincha butun grafni bosib o'tish uchun mustaqil shox tanlanadi). keyin algoritm ushbu uchning qo'shnilariga tashrif buyuradi. ularning keyin - qo'shnilarning qo'shnilariga va hokazo tartibda amalga oshiriladi. rasmiy ravishda, boshlang'ich uchdan to -uchgacha raqaml...

Bu fayl DOC formatida 10 sahifadan iborat (838,0 KB). "grafda o`tish eni bo`yicha qidiruv- bfs algoritmi"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: grafda o`tish eni bo`yicha qidi… DOC 10 sahifa Bepul yuklash Telegram