Graflarda BFS va DFS: xaritani qatlam-qatlam va chuqurlikka aylanish

Qisqacha: BFS (kenglik bo'yicha qidiruv) grafni qatlam-qatlam aylanadi: avval boshlang'ich tugunning qo'shnilari, keyin ularning qo'shnilari. U navbat (queue) bilan ishlaydi. DFS (chuqurlik bo'yicha qidiruv) bitta yo'l bo'ylab oxirigacha boradi, keyin orqaga qaytadi — rekursiya yoki stek bilan. Ikkalasida ham visited to'plami har tugunni bir marta ko'rishni ta'minlaydi, aks holda sikllarda abadiy aylanib qoladi. Murakkablik — O(V + E), bu yerda V — tugunlar, E — qirralar soni.

Bu darsda

• Grafda BFS ni navbat bilan, DFS ni rekursiya va stek bilan yoza olasiz.
• visited nima uchun kerakligini va uni qachon belgilash kerakligini tushuntira olasiz.
• Bog'langan komponentlarni sanay olasiz.
• Katakli jadvalni (grid) graf sifatida ko'rib, "orollar soni" turidagi masalani yecha olasiz.
• BFS/DFS O(V + E) ekanini o'lchov bilan tasdiqlay olasiz.

Oldin bilishingiz kerak: Graf atamalari va ko'rinishlari, Daraxt bo'ylab yurish: DFS va BFS, Queue va deque, Stack, Matritsa bilan ishlash.

1. Nega bu kerak?

O'tgan darsda «Bahor»ning yetkazish xaritasini graf sifatida qurdik. Endi Jasur aka ikki savol berdi.

Birinchisi: "Kuryer bitta yo'l bilan qaysi mahallalarga yetadi, ikki yo'l bilan qaysilariga?" Yangi aksiya faqat yaqin mahallalarga bo'ladi. Ikkinchisi — zal haqida: "Banket uchun stollarni guruhlarga ajratdik. Yonma-yon turgan stollar bitta guruh. Rejada nechta guruh bor?"

Ikkala savolning ham javobi — grafni aylanib chiqish: har tugunga bir marta borib, uni ko'rish. Daraxtni aylanishni bilasiz (Daraxt bo'ylab yurish). Lekin grafda bitta yangi xavf bor — sikllar. Daraxtda pastga tushsangiz, boshlagan joyingizga qaytmaysiz. Grafda esa Bahor → Chilonzor → Olmazor → Bahor — yana boshiga keldingiz. Ehtiyot bo'lmasangiz, dastur shu doirada abadiy aylanadi.

2. Sodda urinish va visited

2.1 Daraxtdagidek aylansak

Daraxtda BFS shunday edi: ildizni navbatga qo'y, navbatdan ol, bolalarini navbatga qo'sh. Xuddi shuni grafda sinaymiz. Uchburchak xarita: Bahor, Chilonzor va Olmazor bir-biri bilan bog'langan. Dastur abadiy ishlab qolmasligi uchun 12 qadamdan keyin to'xtatamiz:

const graph = new Map(Object.entries({
  B: ["C", "O"], C: ["B", "O"], O: ["B", "C"],
}));

const queue = ["B"];
let head = 0;
const order = [];
while (head < queue.length && order.length < 12) { // chegara
  const v = queue[head++];
  order.push(v);
  for (const u of graph.get(v)) queue.push(u); // visited yo'q!
}
console.log(order.join(" "));
console.log("navbatda kutmoqda:", queue.length - head);

Konsolda:

B C O B O B C C O B C C
navbatda kutmoqda: 13

Uchta mahalla — lekin dastur ularni qayta-qayta ko'ryapti, navbat esa o'sib boryapti. Chegarani olib tashlasangiz, navbat xotira tugaguncha o'sadi. Kodda Object.entries obyektni [kalit, qiymat] juftlariga aylantiradi (Obyekt bo'ylab yurish), new Map(...) esa ulardan Map yasaydi — grafni qisqa yozish usuli. head — navbat boshi: shift() O(n) bo'lgani uchun Queue darsida o'rgangan usulni ishlatamiz — indeksni suramiz.

2.2 visited — ko'rilganlar ro'yxati

Yechim — ko'rilgan tugunlarni eslab qolish. visited (ko'rilgan) to'plami — algoritm allaqachon yetib kelgan tugunlar. Har qo'shnini navbatga qo'yishdan oldin tekshiramiz: u visited da bormi? Bor bo'lsa — o'tkazib yuboramiz.

Bu muzeydagi chiptaga o'xshaydi. Har zalga kirganda chiptangizga belgi qo'yiladi. Belgisi bor zalga qayta kirmaysiz — aks holda bir xil zallarni aylanib, kechgacha chiqolmaysiz.

visited uchun Set olinadi. has va add — O(1). Massiv bilan includes ham ishlaydi, lekin u O(V) — keyinroq o'lchab ko'ramiz, bu farq qanchalik og'ir.

3. BFS — qatlam-qatlam

3.1 G'oya

BFS (Breadth-First Search — kenglik bo'yicha qidiruv) — grafni boshlang'ich tugundan uzoqlashib boruvchi qatlamlar bo'yicha aylanish. Avval 0-qatlam (boshlang'ich tugun), keyin 1-qatlam (uning qo'shnilari), keyin 2-qatlam (qo'shnilarning hali ko'rilmagan qo'shnilari). Qatlamlar hech qachon aralashmaydi: 2-qatlamdagi birorta tugun 1-qatlam tugagunicha ko'rilmaydi.

Suvga tosh tashlaganingizni eslang. To'lqin doira bo'lib tarqaladi: avval yaqin halqa, keyin kattaroq. BFS ham shunday — hech bir uzoq tugunni yaqinidan oldin ko'rmaydi.

Buni ta'minlaydigan narsa — navbat (queue): birinchi kirgan birinchi chiqadi. 1-qatlam tugunlari navbatga oldin kiradi, demak oldin chiqadi. Ular chiqqanda 2-qatlam tugunlarini navbat oxiriga qo'yadi — ular kutib turadi.

3.2 «Bahor» xaritasida BFS

Quyida butun xarita (vaznlarsiz — hozir faqat bog'lanish muhim). Tugun ostidagi son — uning qatlami, ya'ni Bahor'dan necha qirra uzoqligi. Pastdagi navbat qatoriga qarang: yangi tugunlar doim oxiriga qo'shiladi, boshidan olinadi.

Kod bo'yicha muhim joylar:

• new Set([start]) — boshlang'ich tugun darhol ko'rilgan deb belgilanadi.
• queue[head++] — navbat boshidan olish: avval queue[head] o'qiladi, keyin head bittaga oshadi.
• if (!visited.has(u)) — faqat yangi qo'shni o'tadi. U shu zahoti visited ga yoziladi, navbatdan chiqqanda emas.

Oxirgi nuqta nozik, uni «Ko'p uchraydigan xatolar» bo'limida yana ko'ramiz. Hozircha natijaga qarang: B, keyin C, O, M, S (hammasi 1-qatlam), keyin Y va Q (2-qatlam). Jasur akaning birinchi savoliga javob tayyor: bir yo'l bilan — 4 ta mahalla, ikki yo'l bilan — yana 2 ta.

3.3 Qatlam — eng kam qirralar soni

BFS'ning eng muhim xususiyati: tugunning qatlami — boshlang'ich tugundan unga eng kam qirrali yo'lning uzunligi. Sergeli'ga Bahor'dan Mirobod orqali ham (2 qirra), to'g'ri ham (1 qirra) borsa bo'ladi. BFS uni 1-qatlamga qo'ydi — to'g'ri yo'l topildi.

Nega shunday? Sergeli birinchi marta navbatga kim orqali tushsa, o'sha qatlamga yoziladi. Navbat qatlamlarni tartib bilan chiqaradi. Demak Sergeli'ga birinchi yetib kelgan yo'l — eng qisqasi. Bu xususiyatni Eng qisqa yo'l darsida to'liq ishlatamiz: u yerda BFS yo'lning o'zini ham qaytaradi, vaznli grafda esa Dijkstra kerak bo'ladi.

Tekshirib ko'ring: BFS ni Qo'yliq'dan (Q) boshlasak, qaysi tugunlar 1-qatlamda bo'ladi? Bahor qaysi qatlamda?

4. DFS — chuqurlikka

4.1 G'oya

DFS (Depth-First Search — chuqurlik bo'yicha qidiruv) — bitta yo'l bo'ylab imkon boricha uzoqqa borish, berk ko'chaga kelganda bir qadam orqaga qaytib, boshqa yo'lni sinash. Labirintdan chiqishni o'ylang: bitta yo'lak bo'ylab oxirigacha yurasiz, devorga taqalsangiz, oxirgi ayrilishga qaytasiz.

DFS ni yozishning eng tabiiy usuli — rekursiya (Rekursiv fikrlash). visit(v) tugunni ko'rilgan deb belgilaydi va har ko'rilmagan qo'shni uchun o'zini chaqiradi. Orqaga qaytish — bu shunchaki funksiyadan chiqish. "Qaytish manzili" ni JavaScript'ning chaqiruvlar steki o'zi eslab qoladi.

4.2 «Bahor» xaritasida DFS

Quyidagi rasmda stek qatoriga qarang. Sariq tugunlar — stekda kutayotganlar: ularning visit chaqiruvi hali tugamagan. Yashil — butunlay tugaganlar. Yashil qirralar DFS haqiqatan yurgan yo'llarni ko'rsatadi.

BFS bilan solishtiring. BFS Bahor'ning to'rtala qo'shnisini birinchi ko'rdi. DFS esa Chilonzor'ga kirib, undan Olmazor'ga, undan Yunusobod'ga... — Bahor'ning qolgan qo'shnilariga (M, S) faqat ancha keyin, boshqa yo'l orqali yetdi. Ikkalasi ham 7 ta tugunni bir martadan ko'rdi, faqat tartib boshqa.

Yashil qirralarni sanang: 6 ta. Ular 7 ta tugunni siklsiz bog'laydi — bu daraxt! Grafning hamma tugunlarini siklsiz bog'laydigan qirralar to'plami skelet daraxti (spanning tree) deyiladi. DFS (va BFS ham) bog'langan grafning ichidan har doim shunday skelet daraxti chiqaradi. Bu g'oyaga Minimal skelet daraxti darsida qaytamiz.

4.3 Stek bilan DFS

Rekursiyaning bitta muammosi bor — chaqiruvlar steki cheklangan (Xotira murakkabligi). Xaritamiz zanjirga o'xshab ketsa (A → B → C → ... uzun ketma-ketlik), har tugun yangi chaqiruv qo'shadi. Bizda (Node 24.21) rekursiv DFS taxminan 5 600 tugunli zanjirda RangeError: Maximum call stack size exceeded bilan yiqildi.

Yechim — rekursiya o'rniga o'z stekimizni (massiv) ishlatish (Stack): push bilan qo'yamiz, pop bilan olamiz. Massiv xotiradagi oddiy obyekt — u millionlab elementga ham sig'adi:

const graph = new Map(Object.entries({
  B: ["C", "O", "M", "S"], C: ["B", "O", "S"], O: ["B", "C", "Y"],
  M: ["B", "Y", "S", "Q"], S: ["B", "C", "M", "Q"], Y: ["O", "M"],
  Q: ["M", "S"],
}));

function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];
  while (stack.length > 0) {
    const v = stack.pop(); // oxirgi qo'yilgan — birinchi chiqadi
    if (visited.has(v)) continue; // ikki yo'l bilan kelgan bo'lsa
    visited.add(v);
    order.push(v);
    const neighbors = graph.get(v);
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) stack.push(neighbors[i]);
    }
  }
  return order;
}
console.log(dfsIterative(graph, "B").join(" ")); // B C O Y M S Q

Natija rekursiv DFS bilan bir xil. Ikki nozik joy bor:

• Qo'shnilar teskari tartibda stekka qo'yiladi. Stek oxirgi qo'yilganni birinchi beradi, shuning uchun birinchi qo'shni (C) oxirida qo'yiladi va birinchi chiqadi. Tartib muhim bo'lmasa, oddiy for...of ham yetadi.
• visited tekshiruvi pop dan keyin ham bor. Bitta tugun stekka ikki xil yo'l bilan tushishi mumkin: masalan, S ham B orqali, ham C orqali. Ikkinchi nusxasi chiqqanda continue uni tashlab yuboradi.

Maslahat: BFS va stekli DFS kodi deyarli bir xil — farqi faqat bitta tuzilmada: navbat (queue[head++]) yoki stek (stack.pop()). Tuzilmani almashtirsangiz, algoritm almashadi.

5. Murakkablik va o'lchov

5.1 O(V + E)

Har tugun navbatga (yoki stekka) eng ko'pi bilan bir marta kiradi — visited shunga kafolat beradi. Tugun chiqqanda uning qo'shnilar ro'yxati bir marta aylaniladi. Hamma ro'yxatlarning uzunliklari yig'indisi — 2E (darajalar yig'indisi). Demak jami ish: V ta tugun + 2E ta qo'shni tekshiruvi = O(V + E).

Xotira — O(V): visited va navbat (yoki stek) eng ko'pi bilan V ta tugunni saqlaydi. Rekursiv DFS da chaqiruvlar steki ham O(V) gacha o'sadi.

Matritsa bilan saqlangan grafda esa BFS O(V²) bo'ladi: har tugunning qo'shnilarini topish uchun butun qatorni ko'rish kerak. O'tgan darsdagi tanlov shu yerda o'z samarasini beradi.

5.2 O'lchov: Set va includes

Endi visited ni massivda saqlash qanchalik qimmat ekanini ko'ramiz. Ikkita BFS — biri Set.has, ikkinchisi visited.includes(u) bilan. Graf — siyrak (E ≈ 2V, urug'li generator bilan yasalgan), hamma tugunlar bog'langan. O'lchash usuli — benchmarking darsidagidek: har V alohida jarayonda, isitish, mediana. Raqamlar taxminiy — sizning kompyuteringizda boshqacha chiqadi.

Set bilan BFS:

includes bilan BFS (ancha kichik graflarda — kattasini kutib bo'lmaydi):

Qatorma-qator qarang. Birinchi jadvalda (Set) V ikki baravar oshganda vaqt taxminan ikki baravar (biroz ko'proq — katta graf protsessor keshiga sig'maydi). Ikkinchisida (includes) — aniq to'rt baravar: har tekshiruv O(V), jami O(V · E) = O(V²). 16 000 tugunda includes versiyasi yarim soniya ishladi. Set versiyasi esa 800 000 tugunni (50 baravar ko'p!) taxminan shu vaqtda aylandi.

Bu JS o'rnatilgan amallarining narxi darsidagi saboqning graflardagi ko'rinishi: bitta includes — bitta qator, lekin u siklning ichida turibdi.

6. Bog'langan komponentlar

6.1 Graf bo'laklarga bo'linganda

«Bahor» Samarqandda ham filial ochdi. Endi xaritada ikkita "orol" bor: Toshkent mahallalari va Samarqand mahallalari. Ular orasida yetkazish yo'li yo'q. Bunday grafning har bir bog'langan bo'lagi bog'langan komponent (connected component) deyiladi.

Ularni sanash uchun BFS yoki DFS ni bir necha marta ishga tushiramiz:

1. Hamma tugunlarni birma-bir ko'rib chiqamiz.
2. Tugun hali visited da bo'lmasa — bu yangi komponent. Hisoblagichni oshiramiz va shu tugundan DFS boshlaymiz.
3. DFS butun komponentni visited ga yozadi. Keyingi safar uning tugunlari o'tkazib yuboriladi.

function countComponents(graph) {
  const visited = new Set();
  let count = 0;
  for (const start of graph.keys()) {
    if (visited.has(start)) continue;
    count++; // yangi orol
    const stack = [start];
    visited.add(start);
    while (stack.length > 0) {
      const v = stack.pop();
      for (const u of graph.get(v)) {
        if (!visited.has(u)) {
          visited.add(u);
          stack.push(u);
        }
      }
    }
  }
  return count;
}

const branches = new Map(Object.entries({
  B: ["C"], C: ["B"], // Toshkent
  R: ["U", "G"], U: ["R"], G: ["R"], // Samarqand
  N: [], // yangi filial, yo'li yo'q
}));
console.log(countComponents(branches)); // 3

Uchta komponent: Toshkent juftligi, Samarqand uchligi va yolg'iz yangi filial. Qirrasiz tugun ham alohida komponent — shuning uchun tugunlar Map ga qirralardan alohida qo'shilishi muhim (Graf ko'rinishlari).

Murakkablik o'zgarmadi — O(V + E). Tashqi sikl V marta aylanadi, lekin ichki DFS lar jami har tugunni va har qirrani bir martadan ko'radi.

Tekshirib ko'ring: Ichki sikl tashqi sikl ichida turibdi. Nega bu O(V × E) yoki O(V²) emas?

7. Grid — bu ham graf

7.1 Kataklar va qo'shnilar

Endi Jasur akaning ikkinchi savoli — zal rejasi. Reja — 0 va 1 lardan iborat jadval: 1 — stol, 0 — bo'sh joy. Yonma-yon stollar bitta guruh. "Yonma-yon" — tepa, past, chap yoki o'ngda (diagonal emas).

Bu ham graf, faqat yashirin. Har katak — tugun. Har katakning ko'pi bilan to'rtta qo'shnisi bor. Qirralar alohida saqlanmaydi — ularni yo'nalishlar massivi bilan "hisoblab" olamiz: [[-1, 0], [1, 0], [0, -1], [0, 1]] (Matritsa bilan ishlash darsidagi usul). Guruhlar soni — bog'langan komponentlar soni. Mashhur nomi — orollar soni (number of islands): dengiz xaritasida quruqlik bo'laklarini sanash. LeetCode'da 200-masala sifatida mashhur.

7.2 Guruhlarni bo'yash

Tashqi sikl jadvalni qatorma-qator ko'radi. Belgilanmagan stol topsa — yangi guruh ochadi va fill (DFS) bilan butun guruhni shu raqam bilan "bo'yaydi". Quyidagi rasmda: ■ — hali ko'rilmagan stol, raqam — guruh raqami, sariq — hozir bo'yalayotgan guruh.

fill ning boshidagi ikki tekshiruvga e'tibor bering. Birinchisi — jadval chegarasi: r = -1 yoki c = 5 kabi mavjud bo'lmagan katakka kirmaslik. Ikkinchisi — bo'sh joy yoki allaqachon bo'yalgan stol. Bu visited ning grid'dagi ko'rinishi: alohida Set o'rniga label jadvali "ko'rilgan" ma'lumotini saqlaydi.

Murakkablik: R qator va C ustunli jadvalda V = R × C katak, har katakning ≤ 4 qo'shnisi bor — E ≤ 4V. Demak O(R × C) vaqt va xotira.

7.3 Katta jadval va rekursiya

Bu fill rekursiv. 300 × 300 jadvalning hammasi stol bo'lsa-chi? Bitta guruhda 90 000 katak — rekursiya chuqurligi juda katta bo'ladi. Bizda bu holatda Maximum call stack size exceeded chiqdi. Shuning uchun real kodda grid uchun stekli DFS yoki BFS yoziladi — buni 3-mashqda qilasiz.

8. BFS yoki DFS?

Uchinchi qator — keyingi darslar uchun. DFS'da tugunning visit chaqiruvi tugagan paytni bilamiz (stekdan chiqdi). Bu ma'lumot Topologik saralash va sikl aniqlash darsida asosiy vosita bo'ladi.

9. Chegaraviy holatlar

• Bo'sh graf yoki boshlang'ich tugun yo'q. graph.get("X") — undefined, for...of esa TypeError beradi. Funksiya boshida tekshiring: if (!graph.has(start)) return [];.
• Bitta tugun, qirrasiz. BFS [start] qaytaradi — to'g'ri.
• Halqa (o'ziga qirra). visited uni o'zi hal qiladi: tugun allaqachon ko'rilgan.
• Bog'lanmagan graf. Bitta BFS faqat o'z komponentini ko'radi. "Hamma tugun" kerak bo'lsa — komponentlar sikli.
• Yo'nalgan graf. Kod o'zgarmaydi, lekin "kimga yetib boradi" strelka yo'nalishi bo'yicha: A → B bo'lsa, B'dan boshlangan BFS A'ni ko'rmaydi.
• Bo'sh grid ([]). grid[0].length — TypeError. Avval grid.length === 0 ni tekshiring.

10. Ko'p uchraydigan xatolar

10.1 visited ni navbatdan chiqqanda belgilash

const v = queue[head++];
visited.add(v); // ❌ kech
for (const u of graph.get(v)) {
  if (!visited.has(u)) queue.push(u);
}

Natija baribir to'g'ri chiqishi mumkin, lekin bitta tugun navbatga bir necha marta tushadi. Bahor xaritasida S ham B, ham C, ham M orqali navbatga kirardi. Zich grafda navbat V emas, E gacha o'sadi — vaqt va xotira ortadi. Tuzatish: BFS'da tugunni navbatga qo'yayotganda visited ga yozing.

10.2 visited ni unutish

Daraxt kodini grafga ko'chirish — "Sodda urinish" bo'limidagi abadiy sikl. Daraxtda ishlagan kod grafda qotib qoladi. Tuzatish: grafda doim visited.

10.3 shift() bilan navbat

queue.shift() har safar butun massivni bir katak suradi — O(V). Butun BFS O(V²) bo'lib qoladi. Tuzatish: head indeksi (Queue).

10.4 Grid'da chegarani keyin tekshirish

grid[r][c] ni chegara tekshiruvidan oldin o'qish: r = -1 da grid[-1] — undefined, undefined[c] esa TypeError: Cannot read properties of undefined. Tuzatish: avval r va c oralig'ini tekshiring, keyin katakni o'qing.

11. Mashqlar

1-mashq (oson): Tartibni qo'lda toping

Darsdagi xaritada BFS va rekursiv DFS ni Yunusobod'dan (Y) boshlang. Qo'shnilar ro'yxatdagi tartibda ko'riladi: Y: ["O", "M"], O: ["B", "C", "Y"], M: ["B", "Y", "S", "Q"] va hokazo (darsdagi graph dan). Har biri qanday tartib chiqaradi?

2-mashq (o'rta): Har mahalla necha qirra uzoqda

distances(graph, start) funksiyasini yozing: u Map qaytarsin — har tugun uchun start dan necha qirra uzoqligi (BFS qatlami). Ishora: visited o'rniga dist Map ni ishlating — kalit bor bo'lsa, tugun ko'rilgan; yangi tugunning masofasi dist.get(v) + 1.

const graph = new Map(Object.entries({
  B: ["C", "O", "M", "S"], C: ["B", "O", "S"], O: ["B", "C", "Y"],
  M: ["B", "Y", "S", "Q"], S: ["B", "C", "M", "Q"], Y: ["O", "M"],
  Q: ["M", "S"],
}));

function distances(graph, start) {
  const dist = new Map([[start, 0]]); // ham masofa, ham visited
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const v = queue[head++];
    for (const u of graph.get(v)) {
      if (!dist.has(u)) {
        dist.set(u, dist.get(v) + 1);
        queue.push(u);
      }
    }
  }
  return dist;
}
console.log(distances(graph, "Q"));

Map(7) {
  'Q' => 0,
  'M' => 1,
  'S' => 1,
  'B' => 2,
  'Y' => 2,
  'C' => 2,
  'O' => 3
}

3-mashq (qiyin): Stol guruhlari — stek bilan

kurs/mashqlar/14/46-bfs-dfs/guruhlar.test.mjs faylida countGroups(grid) funksiyasini rekursiyasiz yozing (o'z stekingiz bilan). Testlar (node:test):

1. Bo'sh zal ([]) va stolsiz zal — 0.
2. Diagonal qo'shni emas: [[1, 0], [0, 1]] — 2.
3. Darsdagi zal — 4.
4. 300 × 300 to'liq zal — 1, stek to'lmasdan.

Ishora: seen jadvali uchun grid.map((row) => row.map(() => false)); katakni stekka qo'yayotganda belgilang («visited ni navbatdan chiqqanda belgilash» xatosidagi saboq).

// kurs/mashqlar/14/46-bfs-dfs/guruhlar.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

function countGroups(grid) {
  if (grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  const seen = grid.map((row) => row.map(() => false));
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== 1 || seen[r][c]) continue;
      count++;
      const stack = [[r, c]]; // o'z stekimiz — rekursiya yo'q
      seen[r][c] = true;
      while (stack.length > 0) {
        const [cr, cc] = stack.pop();
        for (const [dr, dc] of DIRS) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          if (grid[nr][nc] !== 1 || seen[nr][nc]) continue;
          seen[nr][nc] = true; // stekka qo'yishda belgilaymiz
          stack.push([nr, nc]);
        }
      }
    }
  }
  return count;
}

test("bo'sh zal va stolsiz zal — 0", () => {
  assert.equal(countGroups([]), 0);
  assert.equal(countGroups([[0, 0], [0, 0]]), 0);
});

test("diagonal qo'shni emas — 2 guruh", () => {
  assert.equal(countGroups([[1, 0], [0, 1]]), 2);
});

test("darsdagi zal — 4 guruh", () => {
  const hall = [
    [1, 1, 0, 0, 1],
    [1, 0, 0, 1, 1],
    [0, 0, 1, 0, 0],
    [1, 0, 1, 1, 0],
  ];
  assert.equal(countGroups(hall), 4);
});

test("300 × 300 to'liq zal — stek to'lmaydi", () => {
  const big = Array.from({ length: 300 }, () => Array(300).fill(1));
  assert.equal(countGroups(big), 1);
});

✔ bo'sh zal va stolsiz zal — 0 (0.795ms)
✔ diagonal qo'shni emas — 2 guruh (0.1566ms)
✔ darsdagi zal — 4 guruh (0.123ms)
✔ 300 × 300 to'liq zal — stek to'lmaydi (29.0829ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 123.6335

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md jadvaliga qo'shing: BFS (navbat bilan), DFS (rekursiv va stekli), bog'langan komponentlar, grid'dagi guruhlar va "visited massivda" xato varianti. Xotira ustunida rekursiya stekini ham ko'rsating.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Grafni aylanish | BFS (navbat, Set) | O(V + E) | O(V) |
| Grafni aylanish | DFS rekursiv | O(V + E) | O(V) stek |
| Grafni aylanish | DFS o'z stekida | O(V + E) | O(V) |
| Grafni aylanish | BFS, visited massivda | O(V · E) | O(V) |
| Komponentlar soni | har ko'rilmagandan DFS | O(V + E) | O(V) |
| Grid guruhlari | DFS/BFS kataklarda | O(R · C) | O(R · C) |

git add 14/MURAKKABLIK.md 14/46-bfs-dfs
git commit -m "14/46: BFS/DFS — jadval va stekli guruhlar testi"

12. Real ishda

• "Do'stlarning do'stlari". Ijtimoiy tarmoqlardagi "tanish bo'lishi mumkin" ro'yxati — sizdan 2 qatlam uzoqlikdagi odamlar. Bu BFS'ning ikki qatlami.
• Veb-sahifalarni aylanish. Qidiruv tizimlarining "o'rgimchak" (crawler) dasturlari sahifadan sahifaga havolalar orqali o'tadi — bu graf aylanishi. visited siz bir xil sahifalarni abadiy yuklardi.
• Rasm muharrirlari. "Bo'yoq chelagi" (flood fill) asbobi — grid'dagi DFS/BFS: bosgan nuqtangizdan bir xil rangli qo'shni piksellarni bo'yaydi. Darsdagi fill bilan bir xil g'oya.
• Axlat yig'uvchi. JavaScript dvigateli qaysi obyektlar hali kerakligini topish uchun ildiz obyektlardan havolalar bo'ylab yuradi — bu ham graf aylanishi (Garbage collection).
• Intervyu. "Orollar soni", "labirintdan chiqish", "so'z zanjiri" — BFS/DFS eng ko'p so'raladigan mavzulardan. Javobda visited va O(V + E) ni albatta ayting.

Xulosa

• BFS navbat bilan qatlam-qatlam yuradi; tugunning qatlami — unga eng kam qirrali yo'l uzunligi.
• DFS bitta yo'l bo'ylab chuqur ketadi va orqaga qaytadi — rekursiya yoki o'z stekimiz bilan. Rekursiv DFS bizda ~5 600 chuqurlikda stekni to'ldirdi.
• visited — grafda majburiy. BFS'da tugunni navbatga qo'yayotganda belgilang.
• Ikkala algoritm ham O(V + E) vaqt, O(V) xotira. O'lchovda Set bilan V ×2 → vaqt ≈ ×2,4; includes bilan — ×4 (O(V²)).
• Bog'langan komponentlar — "ko'rilmagan tugundan DFS" sikli. Grid — yashirin graf: katak — tugun, 4 qo'shni — qirralar.

Keyingi dars: Eng qisqa yo'l — BFS bilan yo'lning o'zini tiklash, vaznli xaritada Dijkstra algoritmi (heap bilan) va manfiy vaznlar uchun Bellman-Ford g'oyasi.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 20.2 (BFS), 20.3 (DFS).
• Robert Sedgewick, Kevin Wayne, "Algorithms", 4-nashr, 2011 — 4.1 (DFS, BFS, bog'langan komponentlar).
• LeetCode 200 "Number of Islands" — leetcode.com/problems/number-of-islands (masala g'oyasi; darsdagi shart — o'zimizniki).