19-dars: BFS va eng qisqa yo'l

3-darajaOltin — graflar17–24 darslar

HayotdaXabar

Sinfga xabar tarqatasiz. Birinchi daqiqada uni ikki do’stingizga aytasiz, ular ikkinchi daqiqada o’z do’stlariga, va hokazo. Kimdir xabarni uchinchi daqiqada eshitgan bo’lsa, demak u sizdan uch qadam uzoqda — bundan tezroq yetib borishning iloji yo’q edi.

Bu darsdan keyin siz

• BFS ni navbat bilan yozasiz
• vaznsiz grafda eng qisqa yo’l uzunligini topasiz
• yo’lning o’zini (uchlar ketma-ketligini) tiklaysiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·guruh bilan·Sinf xonasi

Hamma o’rnidan tursin. O’qituvchi bir o’quvchini tanlaydi — u qo’lini ko’taradi va «nol» deydi.

Keyin har bosqichda: qo’li ko’tarilganlarning yonidagi o’tirgan o’quvchilar qo’l ko’taradi va o’z raqamini aytadi — bir oldingisidan bitta ko’p. Butun sinf qo’l ko’targanda to’xtaysiz.

Nimani sezishingiz kerak

Har kimning raqami boshlang’ich o’quvchidan qancha «qadam» uzoqda ekanini bildiradi. Diqqat qiling: hech kim raqamini ikkinchi marta o’zgartirmadi — birinchi eshitilgan raqam eng kichigi bo’ldi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

BFS nima

BFSbreadth-first search

Grafni qatlam-qatlam kezish usuli: avval boshlang’ich uchdan bir qadam uzoqdagilar, keyin ikki qadam uzoqdagilar va hokazo.

DFS chuqurlikka kirardi, BFS esa kenglikka yoyiladi. Bitta harf farq: stek o’rniga navbat.

◆Asosiy g'oya

Navbat uchun deque majburiy. list.pop(0) har chaqiruvda butun ro’yxatni suradi va BFS ni O(n²) ga aylantiradi — 12-darsda o’lchagan edik.

Sekin yechim

Vaznsiz grafda eng qisqa yo’lni BFS siz ham topish mumkin: masofalarni takror-takror yaxshilab boramiz, hech narsa o’zgarmaguncha.

sekin.pyNusxalash

1qirralar = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]2n = 53CHEKSIZ = float("inf")4masofa = [CHEKSIZ] * (n + 1)5masofa[1] = 06ozgardi = True7while ozgardi:8  ozgardi = False9  for a, b in qirralar:10      if masofa[a] + 1 < masofa[b]:11          masofa[b] = masofa[a] + 112          ozgardi = True13      if masofa[b] + 1 < masofa[a]:14          masofa[a] = masofa[b] + 115          ozgardi = True16print(masofa[1:])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1qirralar = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]2n = 53CHEKSIZ = float("inf")4masofa = [CHEKSIZ] * (n + 1)5masofa[1] = 06ozgardi = True7while ozgardi:8  ozgardi = False9  for a, b in qirralar:10      if masofa[a] + 1 < masofa[b]:11          masofa[b] = masofa[a] + 112          ozgardi = True13      if masofa[b] + 1 < masofa[a]:14          masofa[a] = masofa[b] + 115          ozgardi = True16print(masofa[1:])

Sizning bashoratingizTekshirish

Javobni ko'rish

[0, 1, 1, 2, 3]

Javob to'g'ri. Kamchiligi — hech qanday tartib tanlanmagani uchun barcha qirralar qayta-qayta ko'riladi.

Nega sekin

Har o’tishda kamida bitta uch o’z yakuniy masofasini oladi, ya’ni eng yomon holatda n marta o’tish kerak. Har o’tish esa m qirrani ko’radi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 100 000
Takror-takror yaxshilashn^2	10⁶sig‘adi	10¹⁰sig‘maydi
BFSn	1 000sig‘adi	100 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

BFS to’g’ri tartibni tanlaydi: navbatdan uch olinganda uning masofasi allaqachon yakuniy bo’ladi. Shuning uchun hech narsani qayta ko’rish kerak emas.

tez.pyNusxalash

1from collections import deque2qoshni = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3, 5], 5: [4]}3masofa = {1: 0}4navbat = deque([1])5while navbat:6  u = navbat.popleft()7  for v in qoshni[u]:8      if v not in masofa:9          masofa[v] = masofa[u] + 110          navbat.append(v)11print(masofa)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from collections import deque2qoshni = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3, 5], 5: [4]}3masofa = {1: 0}4navbat = deque([1])5while navbat:6  u = navbat.popleft()7  for v in qoshni[u]:8      if v not in masofa:9          masofa[v] = masofa[u] + 110          navbat.append(v)11print(masofa)

Sizning bashoratingizTekshirish

Javobni ko'rish

{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}

Uch masofasi BIRINCHI yozilganda yakuniy bo'ladi. Shuning uchun if v not in masofa yetadi — qayta yaxshilash umuman kerak emas.

Nega birinchi yetib kelgan qatlam eng qisqasi

Navbat har doim masofa bo’yicha tartiblangan bo’lib qoladi: avval barcha 0-qatlam uchlari, keyin barcha 1-qatlam uchlari va hokazo.

Demak uchga birinchi marta yetib kelgan yo’l eng kam qadamlisi bo’ladi: undan qisqarog’i bo’lganda, o’sha qisqaroq yo’lning oxirgi uchi oldinroq navbatdan chiqqan va bizni oldinroq topgan bo’lardi.

Yo’lning o’zini tiklash

Ko’p masalada uzunlik emas, yo’lning o’zi so’raladi. Buning uchun har uch uchun uni kim ochganini eslab qolish yetadi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from collections import deque2qoshni = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3, 5], 5: [4]}3ota = {1: None}4navbat = deque([1])5while navbat:6  u = navbat.popleft()7  for v in qoshni[u]:8      if v not in ota:9          ota[v] = u10          navbat.append(v)11yol = []12u = 513while u is not None:14  yol.append(u)15  u = ota[u]16print(yol[::-1])

Sizning bashoratingizTekshirish

Javobni ko'rish

[1, 2, 4, 5]

Yo'l oxiridan boshiga qarab yig'iladi, keyin teskari o'giriladi. ota lug'ati bir vaqtning o'zida «ko'rildimi?» belgisi vazifasini ham bajaradi.

Sinab ko’r

Vizualda har uch ustidagi son — boshlang’ichdan masofa. Bir qatlam tugamaguncha keyingisi boshlanmasligini kuzating.

BFS — qatlam-qatlam tarqalish

Uch ustidagi son — A dan masofa. Bir qatlam tugamaguncha keyingisi boshlanmaydi.

BFS navbat bilan ishlaydi va grafni qatlam-qatlam kezadi; uchga birinchi yetib kelgan qatlam eng qisqa masofa bo'ladi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. A dan boshlaymiz, masofasi 0. Navbatda faqat A turibdi.
2. A navbat boshidan olindi. Yangi uchlar: B, D — ularning masofasi 0 + 1 = 1.
3. B navbat boshidan olindi. Yangi uchlar: C, E — ularning masofasi 1 + 1 = 2.
4. D olindi, yangi qo'shni yo'q — hammasi allaqachon topilgan.
5. C navbat boshidan olindi. Yangi uchlar: F — ularning masofasi 2 + 1 = 3.
6. E olindi, yangi qo'shni yo'q — hammasi allaqachon topilgan.
7. F olindi, yangi qo'shni yo'q — hammasi allaqachon topilgan.
8. Tayyor. Har uch ustidagi son — A dan eng qisqa masofa. Bu son BIRINCHI marta yozilganda yakuniy bo'ladi va boshqa o'zgarmaydi.

A dan boshlaymiz, masofasi 0. Navbatda faqat A turibdi.

Ochilgan uch0

OrqagaO‘ynatishOldinga1/8Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

19 / 40

MasalaVaznsiz grafda 1-uchdan eng qisqa masofalarni toping.

Taklif qilingan yechim

1. 1navbat = [1], masofa[1] = 0 deb boshlaymiz.
2. 2Navbat boshidan uch olamiz: u = navbat.pop(0).
3. 3Har ko‘rilmagan qo‘shniga masofa qo‘yamiz va navbat oxiriga qo‘shamiz.
4. 4Navbat bo‘shaguncha davom etamiz. Yechim O(n + m).

Bu javobning 2-qismi noto'g'ri. Mantiq butunlay to'g'ri, lekin list.pop(0) navbat boshidan olganda qolgan barcha elementlarni bittaga suradi. Bitta chaqiruv O(n), demak yechim O(n + m) emas, O(n²) bo'ladi. To'g'risi: deque va popleft().

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1BFS va DFS orasidagi kod farqi nima?

Javobni ko'rish

Tuzilma: DFS stek ishlatadi (oxirgi qo’shilgan birinchi chiqadi), BFS navbat (birinchi qo’shilgan birinchi chiqadi). Qolgan hammasi bir xil.

2Nega BFS masofasi bir marta yoziladi va boshqa o'zgarmaydi?

Javobni ko'rish

Navbat masofa bo’yicha tartiblangan bo’lib qoladi. Uchga birinchi yetib kelgan yo’l eng kam qadamlisi bo’ladi, chunki qisqarog’i bo’lsa u oldinroq navbatdan chiqqan bo’lardi.

3BFS vaznli grafda ishlaydimi?

Javobni ko'rish

Ishlamaydi. U qirralar sonini sanaydi, narxni emas: kam qirrali yo’l qimmatroq bo’lishi mumkin. Vaznli graf uchun Dijkstra kerak (24-dars).

4Yo'lning o'zini qanday tiklaysiz?

Javobni ko'rish

Har uch uchun uni kim ochganini (ota) saqlab boring, keyin oxirgi uchdan boshiga qarab yuring va ro’yxatni teskari o’giring.

5list.pop(0) bilan yozilgan BFS qanday xato beradi?

Javobni ko'rish

Hech qanday xato bermaydi va to’g’ri javob qaytaradi — faqat O(n²) ishlaydi va katta testda vaqt chegarasidan o’tmaydi.

Masalalar

Masalalar

3 ta

• Message RouteCSES 1667o'rta

  Yo‘lning o‘zi so‘ralgan — ota lug‘atini saqlang va oxiridan tiklang.

• LabyrinthCSES 1193o'rta

  Panjara ham graf. Yo‘lni tiklashda uchlar emas, harflar (U, D, L, R) chiqariladi.

• MonstersCSES 1194qiyin

  Ikki BFS: avval barcha maxluqlardan bir vaqtda, keyin o‘yinchidan. Ikkinchisi birinchisidan tez bo‘lishi kerak.

Lokal mashq: mashqlar/19-eng-qisqa/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Sinf bo’ylab «to’lqin» mashqini o’tkazing va har o’quvchining raqamini doskaga yozing. Keyin boshqa o’quvchidan boshlab takrorlang — raqamlar qanday o’zgardi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

19-eng-qisqa masalasini yeching, keyin yechimingizni o’zgartirib yo’lning o’zini ham chiqaring. Yetib bo’lmaydigan holatni unutmang.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

BFS ni ataylab list.pop(0) bilan yozing va 100 000 uchli grafda ikkala variantni o’lchang. Farq necha barobar chiqdi? Natijani 12-darsdagi bashoratingiz bilan solishtiring.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim