18-dars: DFS

3-darajaOltin — graflar17–24 darslar

HayotdaLabirint

Labirintga kirasiz va qo’lingizda ip bor. Har chorrahada bitta yo’lni tanlab, ipni cho’zib ketaverasiz. Tupikka duch kelsangiz ipni izlab oxirgi chorrahagacha qaytasiz va boshqa yo’lni sinaysiz. Bu — DFS.

Bu darsdan keyin siz

• DFS ni stek bilan yozasiz va nega rekursiv variant xavfli ekanini bilasiz
• grafdagi bog’langan guruhlarni sanaysiz
• har uch aynan bir marta ko’rilishini ta’minlaysiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·juftlikda·17-darsda chizgan grafingiz

O’sha do’stlik grafini oling. Bitta uchdan boshlang va qoidaga amal qiling: hali bormagan qo’shnilardan bittasini tanlab o’sha yerga o’ting, ismini ro’yxatga yozing.

Bormagan qo’shni qolmasa — oldingi uchga qayting va u yerdan davom eting. Yurgan yo’lingizni qalam bilan qalinlashtirib boring.

Nimani sezishingiz kerak

Qalinlashtirilgan chiziqlar daraxt hosil qildi va unda halqa yo’q — chunki siz hech qachon ko’rilgan uchga qaytib kirmadingiz. Ro’yxat esa DFS tartibidir.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

DFS nima

DFSdepth-first search

Grafni kezish usuli: har qadamda imkon boricha chuqurroq kiriladi, yo’l tugagandagina orqaga qaytiladi.

Yozishning ikki yo’li bor va ikkalasi ham bir xil ish qiladi. Rekursiv variant qisqa, stekli variant esa xavfsiz.

rekursiv.pyNusxalash

1qoshni = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}2korilgan = set()3def dfs(u):4  korilgan.add(u)5  for v in qoshni[u]:6      if v not in korilgan:7          dfs(v)8dfs(1)9print(sorted(korilgan))

▲Bu yerda xato qilishadi

Rekursiv DFS Python’da 100 mingta uchli grafda yiqiladi. Sabab RecursionError: chaqiruv steki chegarasi sukut bo’yicha ming atrofida, uzun zanjir shaklidagi grafda esa chuqurlik uchlar soniga teng bo’ladi. Olimpiadada bu bir necha masalani bir zarbada yo’qotadi.

Shuning uchun bu modulda DFS stek bilan yoziladi. Bu aynan 11-darsdagi stek — rekursiya ham ichkarida xuddi shu tuzilmani ishlatadi, faqat uni Python o’zi boshqaradi.

stek.pyNusxalash

1qoshni = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}2korilgan = {1}3stek = [1]4tartib = []5while stek:6  u = stek.pop()7  tartib.append(u)8  for v in qoshni[u]:9      if v not in korilgan:10          korilgan.add(v)11          stek.append(v)12print(tartib)

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

Bashorat qilingNusxalash

1qoshni = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}2korilgan = {1}3stek = [1]4tartib = []5while stek:6  u = stek.pop()7  tartib.append(u)8  for v in qoshni[u]:9      if v not in korilgan:10          korilgan.add(v)11          stek.append(v)12print(tartib)

Sizning bashoratingizTekshirish

Javobni ko'rish

[1, 3, 2, 4]

Tartib rekursiv variantnikidan farq qiladi: stekdan eng OXIRGI qo'shilgan olinadi, shuning uchun 2 dan oldin 3 ochiladi. Ikkala tartib ham to'g'ri DFS.

Sekin yechim

Endi masala: grafda nechta alohida guruh bor? Birinchi fikr — har uchdan boshlab uning butun guruhini kezib chiqish.

sekin.pyNusxalash

1qoshni = {1: [2], 2: [1, 3], 3: [2], 4: [], 5: [6], 6: [5]}2guruhlar = set()3for boshi in qoshni:4  korilgan = {boshi}5  stek = [boshi]6  while stek:7      u = stek.pop()8      for v in qoshni[u]:9          if v not in korilgan:10              korilgan.add(v)11              stek.append(v)12  guruhlar.add(frozenset(korilgan))13print(len(guruhlar))

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

Bashorat qilingNusxalash

1qoshni = {1: [2], 2: [1, 3], 3: [2], 4: [], 5: [6], 6: [5]}2guruhlar = set()3for boshi in qoshni:4  korilgan = {boshi}5  stek = [boshi]6  while stek:7      u = stek.pop()8      for v in qoshni[u]:9          if v not in korilgan:10              korilgan.add(v)11              stek.append(v)12  guruhlar.add(frozenset(korilgan))13print(len(guruhlar))

Sizning bashoratingizTekshirish

Javobni ko'rish

3

Guruhlar: 1-2-3, yolg'iz 4, va 5-6. Javob to'g'ri, lekin uch a'zoli guruh uch marta to'liq kezib chiqildi.

Nega sekin

Har uchdan alohida kezish — guruh o’z a’zolari soniga teng marta qayta ko’riladi. Bitta katta guruhdan iborat grafda bu n × (n + m) ga chiqadi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 100 000
Har uchdan qayta kezishn^2	10⁶sig‘adi	10¹⁰sig‘maydi
Bir marta kezishn	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

Bitta o’zgarish yetadi: korilgan butun graf bo’ylab bitta marta yuritiladi. Yangi guruh faqat hali ko’rilmagan uchdan boshlanadi.

tez.pyNusxalash

1qoshni = {1: [2], 2: [1, 3], 3: [2], 4: [], 5: [6], 6: [5]}2korilgan = set()3guruhlar = 04for boshi in qoshni:5  if boshi in korilgan:6      continue7  guruhlar += 18  korilgan.add(boshi)9  stek = [boshi]10  while stek:11      u = stek.pop()12      for v in qoshni[u]:13          if v not in korilgan:14              korilgan.add(v)15              stek.append(v)16print(guruhlar)

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

Bashorat qilingNusxalash

1qoshni = {1: [2], 2: [1, 3], 3: [2], 4: [], 5: [6], 6: [5]}2korilgan = set()3guruhlar = 04for boshi in qoshni:5  if boshi in korilgan:6      continue7  guruhlar += 18  korilgan.add(boshi)9  stek = [boshi]10  while stek:11      u = stek.pop()12      for v in qoshni[u]:13          if v not in korilgan:14              korilgan.add(v)15              stek.append(v)16print(guruhlar)

Sizning bashoratingizTekshirish

Javobni ko'rish

3

Javob o'sha, ish hajmi esa boshqa: har uch aynan bir marta stekka tushadi va har qirra bir marta ko'riladi — O(n + m).

Sinab ko’r

Vizualda stekdagi uchlar sariq, tugaganlari yashil. Stekdan har doim eng oxirgi qo’shilgani olinishini kuzating — DFS shu sababli chuqurlashadi.

DFS — chuqurlikka kirish

Stekdan har doim eng oxirgi qo'shilgan uch olinadi — DFS shu sababli chuqurlashadi.

DFS stek bilan ishlaydi: eng oxirgi qo'shilgan uch birinchi bo'lib ochiladi.

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

1. A dan boshlaymiz. Stekka faqat A tushdi.
2. A stekdan olindi. Endi uning qo'shnilarini ko'ramiz.
3. B, D stekka qo'shildi. DFS keyingi qadamda ENG OXIRGI qo'shilganini (D) oladi — shuning uchun u chuqurlikka kiradi.
4. D stekdan olindi. Endi uning qo'shnilarini ko'ramiz.
5. E stekka qo'shildi. DFS keyingi qadamda ENG OXIRGI qo'shilganini (E) oladi — shuning uchun u chuqurlikka kiradi.
6. E stekdan olindi. Endi uning qo'shnilarini ko'ramiz.
7. F stekka qo'shildi. DFS keyingi qadamda ENG OXIRGI qo'shilganini (F) oladi — shuning uchun u chuqurlikka kiradi.
8. F stekdan olindi. Endi uning qo'shnilarini ko'ramiz.
9. C stekka qo'shildi. DFS keyingi qadamda ENG OXIRGI qo'shilganini (C) oladi — shuning uchun u chuqurlikka kiradi.
10. C stekdan olindi. Endi uning qo'shnilarini ko'ramiz.
11. C ning barcha qo'shnilari allaqachon ko'rilgan — orqaga qaytamiz.
12. B stekdan olindi. Endi uning qo'shnilarini ko'ramiz.
13. B ning barcha qo'shnilari allaqachon ko'rilgan — orqaga qaytamiz.
14. Barcha uchlar ko'rildi: 6 qadam. Yashil qirralar — DFS yurgan yo'l; u daraxt hosil qiladi va unda sikl bo'lmaydi.

A dan boshlaymiz. Stekka faqat A tushdi.

Qadam0

OrqagaO‘ynatishOldinga1/14Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

18 / 40

MasalaStek bilan DFS yozing va har uchni bir marta ko'ring.

Taklif qilingan yechim

1. 1Boshlang‘ich uchni stekka qo‘yamiz.
2. 2Stekdan uch olamiz va uni korilgan ga qo‘shamiz.
3. 3Uning barcha qo‘shnilarini stekka qo‘shamiz.
4. 4Stek bo‘shaguncha davom etamiz.

Bu javobning 3-qismi noto'g'ri. Qo'shni stekka qo'shilishidan oldin «ko'rilganmi?» tekshiruvi yo'q va u o'sha zahoti belgilanmaydi. Natijada bitta uch stekka bir necha marta tushadi: siklli grafda stek shishib ketadi. To'g'risi: if v not in korilgan, so'ng darhol korilgan.add(v).

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

Javobni ko'rsatish

O’zingizni sinang

1Rekursiv DFS katta grafda nega yiqiladi?

Javobni ko'rish

RecursionError: chaqiruv steki chegarasi ming atrofida, uzun zanjir shaklidagi grafda esa chuqurlik uchlar soniga teng bo’ladi.

2Uchni qachon korilgan ga qo'shish kerak?

Javobni ko'rish

Stekka qo’yayotganda, olayotganda emas. Aks holda bir uch bir necha marta stekka tushadi.

3DFS yurgan qirralar qanday shakl hosil qiladi?

Javobni ko'rish

Daraxt: har uchga aynan bir marta kiriladi, demak halqa paydo bo’lmaydi. Bu daraxt 23-darsda alohida o’rganiladi.

4Bog'langan guruhlarni sanashda korilgan qayerda e'lon qilinadi?

Javobni ko'rish

Tashqi siklning tashqarisida, ya’ni butun graf uchun bitta. Ichkarida e’lon qilinsa har uchdan qayta kezish boshlanadi va yechim O(n²) bo’ladi.

5DFS ning murakkabligi qanday?

Javobni ko'rish

O(n + m): har uch bir marta ochiladi va har qirra bir marta ko’riladi. Bundan tezroq bo’lishi mumkin emas — kirishning o’zini o’qish ham shuncha.

Masalalar

Masalalar

3 ta

• Building RoadsCSES 1666o'rta

  Guruhlar sonini toping. Ularni ulash uchun har guruhdan bittadan vakil yetadi.

• Cyclic ComponentsCodeforces 977Eo'rta

  Guruh halqa bo‘lishining oddiy belgisi bor: undagi har uchning darajasi aynan 2.

• Flight Routes CheckCSES 1682qiyin

  Bir tomonlama grafda ikki marta kezing: oddiy yo‘nalishda va barcha qirralar teskari qilingan grafda.

Lokal mashq: mashqlar/18-komponentalar/ — 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

17-darsdagi grafingizda DFS ni qo’lda bajaring va stekda har qadamda nima turganini yozib boring. Keyin boshqa uchdan boshlab takrorlang — tartib o’zgardimi, guruhlar soni-chi?

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

18-komponentalar masalasini yeching. sekin.py va tez.py vaqtini python mashqlar/tekshir.py 18-komponentalar bilan solishtiring.

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

Rekursiv DFS ni yozing va uni 100 000 uchli zanjir grafida yurgizing (1-2, 2-3 va hokazo). Qanday xato chiqdi? Keyin sys.setrecursionlimit() bilan chegarani oshirib ko’ring — nima bo’ladi va nega bu yechim emas?

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

Darsni tugatdim