Graf algoritmlari — BFS, DFS, Dijkstra va topological sort (3.7-bob)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 7-mavzu

1. Kirish va motivatsiya

Daraxt 3.6-bob — maxsus holat: har node faqat bitta otaga ega, sikllar yo'q. Graph (graf) — eng umumiy bog'langan tuzilma: node'lar ixtiyoriy tarzda, har xil yo'nalishda bog'langan. Aslida daraxt — bu grafning bir turi.

Graflar bizni o'rab turgan dunyoning modeli: ijtimoiy tarmoq (do'stlar bog'langan), xarita/navigatsiya (shaharlar yo'llar bilan), internet (0.4: serverlar tarmog'i), tavsiyalar ("bu mahsulotni olganlar buni ham oldi"), bog'liqliklar grafi (npm paketlari — 0.7).

O'xshatish: graf — do'stlik tarmog'i. Har odam — node; do'stlik — bog'lanish (edge). Ali Vali bilan do'st, Vali Guli bilan... "Ali Guli bilan necha qadam orqali tanish?" — bu graf masalasi (BFS — eng qisqa yo'l). Yoki metro xaritasi: bekatlar (node) yo'llar (edge) bilan; "A dan B ga eng qisqa yo'l?".

Nega muhim?

• Real tizimlar grafdir: tarmoq 0.4-bob, ijtimoiy aloqalar, navigatsiya, tavsiya.
• BFS/DFS, eng qisqa yo'l — kuchli, keng qo'llaniladigan algoritmlar.
• Bog'liqlik hal qilish (dependency resolution — npm, build), sikl aniqlash.
• Intervyu va tizim dizayni 15.7-bob da muhim.

2. Nazariya — chuqur tushuntirish

2.1. Graf atamalari

       (A)───────(B)
        │  \      │
        │    \    │
       (C)────(D)─(E)

  A, B, C, D, E — VERTEX (tugun, node)
  A—B, A—C, A—D, B—D, ... — EDGE (qirra, bog'lanish)

• Vertex (tugun) — graf elementi (odam, shahar, server).
• Edge (qirra) — ikki tugun orasidagi bog'lanish.
• Degree — tugunga ulangan qirralar soni.
• Path (yo'l) — tugunlar ketma-ketligi (A → D → E).

2.2. Graf turlari

• Directed (yo'naltirilgan) — qirralar yo'nalishli (A → B, lekin B → A emas). Misol: Instagram "follow" (bir tomonlama), Twitter.
• Undirected (yo'naltirilmagan) — qirralar ikki tomonlama (A — B). Misol: Facebook do'stlik (o'zaro).
• Weighted (vaznli) — qirralarning vazni bor (masofa, narx). Misol: shaharlar orasidagi km.
• Cyclic / Acyclic — sikl bormi yoki yo'q. DAG (Directed Acyclic Graph) — yo'naltirilgan, siklsiz (bog'liqliklar, task tartibi).

  Directed:    A → B → C        Undirected:  A — B — C
  Weighted:    A --5-- B --3-- C  (qirralar vaznli)

2.3. Grafni ko'rsatish (representation)

Ikki asosiy usul:

1) Adjacency List (qo'shnilar ro'yxati) — har tugun uchun qo'shnilari ro'yxati (Map/Object — 2.9). Eng ko'p ishlatiladigan (siyrak graflar uchun samarali):

const graf = {
  A: ["B", "C"],       // A ning qo'shnilari
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D"],
};
// Xotira: O(V + E) — siyrak graf uchun samarali

2) Adjacency Matrix (qo'shnilik matritsasi) — V×V jadval (1 = bog'langan, 0 = yo'q). Zich graf yoki tez "bog'langanmi?" tekshiruvi uchun:

      A  B  C  D  E
   A [0  1  1  1  0]
   B [1  0  0  1  0]
   C [1  0  0  1  0]   matrix[A][B]=1 → A,B bog'langan
   D [1  1  1  0  1]
   E [0  0  0  1  0]
// Xotira: O(V²) — zich graf uchun

Qaysi? Ko'p hollarda adjacency list (kam xotira, qo'shnilarni aylanish oson). Matrix — "X,Y bog'langanmi?" ni O(1) tekshirish kerak bo'lsa yoki graf zich bo'lsa.

2.4. BFS — Breadth-First Search (kenglikka)

BFS — boshlang'ich tugundan daraja-baraja yuradi (Queue bilan — 3.4, 3.6). Eng qisqa yo'l (qirralar soni bo'yicha, vaznsiz grafda) topadi:

  A dan boshlanadi:
  Daraja 0: A
  Daraja 1: B, C    (A ning qo'shnilari)
  Daraja 2: D       (B, C ning qo'shnilari)
  Daraja 3: E

function bfs(graf, boshlanish) {
  const korilgan = new Set([boshlanish]);   // (2.9, 3.5)
  const queue = [boshlanish];                // (3.4)
  const natija = [];
  let front = 0;
  while (front < queue.length) {
    const tugun = queue[front++];            // dequeue (3.4)
    natija.push(tugun);
    for (const qoshni of graf[tugun]) {
      if (!korilgan.has(qoshni)) {           // ko'rilmaganni navbatga
        korilgan.add(qoshni);
        queue.push(qoshni);
      }
    }
  }
  return natija;   // O(V + E)
}

korilgan Set MUHIM: grafda sikl bo'lishi mumkin (3.6: daraxtda yo'q edi). Ko'rilganlarni belgilamasa — cheksiz tsikl! (3.4: sikl tuzog'i).

2.5. DFS — Depth-First Search (chuqurlikka)

DFS — bir yo'nalishda oxirigacha boradi, keyin orqaga qaytadi (Stack yoki rekursiya — 3.4, 3.11):

// Rekursiv DFS (3.11)
function dfs(graf, tugun, korilgan = new Set(), natija = []) {
  korilgan.add(tugun);
  natija.push(tugun);
  for (const qoshni of graf[tugun]) {
    if (!korilgan.has(qoshni)) {
      dfs(graf, qoshni, korilgan, natija);   // chuqurlikka (rekursiya)
    }
  }
  return natija;   // O(V + E)
}

BFS vs DFS: BFS — daraja-baraja, eng qisqa yo'l (vaznsiz), Queue. DFS — chuqurlikka, yo'l bor-yo'qligi, sikl aniqlash, Stack/rekursiya. Tanlov masalaga bog'liq.

2.6. Eng qisqa yo'l: BFS va Dijkstra

• Vaznsiz graf → BFS eng qisqa yo'lni beradi (qirralar soni bo'yicha — 2.4).
• Vaznli graf (manfiy bo'lmagan vaznlar) → Dijkstra algoritmi (eng kam masofa yoki xarajat).

  Vaznsiz: A dan E gacha eng kam QADAM (BFS)
  Vaznli:  A dan E gacha eng kam MASOFA/NARX (Dijkstra)

Dijkstra qanday ishlaydi?

1. Boshlang'ich tugundan boshqa barcha tugunlargacha bo'lgan masofani $\infty$ (cheksizlik), o'ziga esa 0 deb belgilanadi.
2. Har qadamda hali ko'rilmagan va eng kichik masofaga ega bo'lgan tugun tanlanadi (buni tezkor olish uchun Min-Heap ishlatiladi — 3.8).
3. Tanlangan tugunning barcha qo'shnilari uchun yangi masofa tekshiriladi: agar masofa[tugun] + qirra_vazni < masofa[qoshni] bo'lsa, qo'shnining masofasi yangilanadi (relaksatsiya).
4. Barcha tugunlar aylanib chiqilgach, boshlang'ich nuqtadan butun tarmoqqa eng qisqa yo'llar xaritasi hosil bo'ladi (GPS navigatorlar asosi).

2.7. Sikl aniqlash va Topological Sort (Kahn algoritmi)

• Sikl aniqlash — yo'naltirilgan grafda davriy qaramlik (circular dependency) borligini aniqlash. DFS paytida tugunlar 3 xil holatda bo'ladi: 0 (ko'rilmagan), 1 (hozirgi rekursiya zanjirida), 2 (to'liq ko'rib chiqilgan). Agar qidiruvda yana 1 holatidagi tugunga duch kelsak — demak sikl bor!
• Topological Sort — Yo'naltirilgan Asiklik Grafda (DAG) bog'liqliklarni mantiqiy ketma-ketlikda tartibga solish: "A bajarilishi uchun B undan oldin bo'lishi kerak". Misol: loyihani build qilish (A paket B ga bog'liq bo'lsa, avval B qurilishi kerak), darslar ketma-ketligi, task rejalashtirish.
• Kahn algoritmi (BFS yondashuvi): Har bir tugunga kiruvchi qirralar sonini (inDegree) hisoblaymiz. inDegree === 0 (hech narsaga bog'liq bo'lmagan) tugunlarni navbatga (Queue) solamiz. Navbatdan olib natijaga qo'shamiz va uning barcha qo'shnilarining inDegreesini 1 taga kamaytiramiz. Agar qo'shnining inDegreesi 0 bo'lib qolsa, uni ham navbatga qo'shamiz.

  Kiyinish tartibi (DAG):  paypoq → tufli;  ko'ylak → kostyum
  Topological sort: to'g'ri ketma-ketlikni topadi

• Bog'langan komponentlar — graf necha alohida "guruh"ga bo'linadi (bir-biriga yetib bo'lmaydigan qismlar). Yo'naltirilmagan grafda: har bir ko'rilmagan tugundan yangi BFS/DFS boshlanadi — necha marta boshlandi, shuncha komponent. Misol: ijtimoiy tarmoqda alohida do'stlar to'dalari, xaritada bog'lanmagan orollar.

  (A—B—C)   (D—E)   (F)     → 3 ta bog'langan komponent
  to'da 1   to'da 2  yolg'iz

2.8. Murakkablik

V — tugunlar soni, E — qirralar soni.

2.9. Senior Architect: Topological Sort (Kahn algoritmi) va Monorepo Build Graph

Graflar zamonaviy devops va build tizimlarining (Turborepo, Nx, npm/pnpm workspaces) eng asosiy yuragi hisoblanadi.

1. Kahn algoritmi bilan Kurslar Jadvali / Paketlar Bog'liqligi (Course Schedule — LeetCode 207/210)

Tasavvur qiling, monorepoda 5 ta paket bor: web paketi ui ga bog'liq, ui paketi utils ga bog'liq. Qaysi paketni birinchi build qilish kerak? Agar A paket B ga, B esa A ga bog'liq bo'lsa (Circular Dependency) — build qotib qoladi va xato berishi kerak.

Kahn algoritmi buni $O(V + E)$ vaqtda xatosiz tartiblaydi:

function buildOrder(numPackages, dependencies) {
  // 1. Adjacency list va In-degree hisoblash:
  const inDegree = new Array(numPackages).fill(0);
  const graph = Array.from({ length: numPackages }, () => []);

  for (const [pkg, dep] of dependencies) {
    // dep bajarilishi kerak -> keyin pkg
    graph[dep].push(pkg);
    inDegree[pkg]++;
  }

  // 2. Hech qanday bog'liqligi bo'lmagan (inDegree === 0) paketlarni Queue'ga solamiz:
  const queue = [];
  for (let i = 0; i < numPackages; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order = [];

  // 3. BFS tarzida navbatdan chiqarib, bog'liqliklarni kamaytirish:
  while (queue.length > 0) {
    const current = queue.shift();
    order.push(current);

    for (const neighbor of graph[current]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // 4. Sikl tekshiruvi: Agar barcha paketlar saralanmagan bo'lsa -> Aylanma bog'liqlik bor!
  if (order.length !== numPackages) {
    throw new Error("Aylanma bog'liqlik (Circular Dependency) aniqlandi! Build imkonsiz.");
  }

  return order; // To'g'ri build ketma-ketligi!
}

// 0: utils, 1: auth, 2: ui, 3: web
const deps = [
  [1, 0], // auth depends on utils
  [2, 0], // ui depends on utils
  [3, 1], // web depends on auth
  [3, 2], // web depends on ui
];

console.log(buildOrder(4, deps)); // [0, 1, 2, 3] (Avval utils, keyin auth va ui, oxirida web)

Bu algoritm Turborepo yoki Docker ko'p bosqichli build tizimlarida qaysi vazifalarni parallel va qaysilarini ketma-ket bajarish kerakligini hisoblashning asosi hisoblanadi.

3. Sintaksis — tez ma'lumotnoma

// Adjacency list (eng ko'p — 2.3)
const graf = { A: ["B", "C"], B: ["D"], ... };

// BFS — Queue + korilgan Set (eng qisqa yo'l, vaznsiz)
// DFS — Stack/rekursiya + korilgan Set (yo'l/sikl)
// korilgan Set — sikldan saqlaydi (MAJBURIY!)

// Murakkablik: BFS/DFS — O(V + E)
// Vaznli eng qisqa yo'l — Dijkstra (Heap — 3.8)

4. Batafsil kod namunalari

Misol 1 — Graf class (adjacency list — 2.3)

class Graph {
  constructor() { this.qoshnilar = new Map(); }   // tugun → [qo'shnilar] (2.9)

  qoshTugun(t) {
    if (!this.qoshnilar.has(t)) this.qoshnilar.set(t, []);
  }
  qoshQirra(a, b) {                  // yo'naltirilmagan (ikki tomonlama — 2.2)
    this.qoshTugun(a); this.qoshTugun(b);
    this.qoshnilar.get(a).push(b);
    this.qoshnilar.get(b).push(a);   // directed bo'lsa, bu qatorni olib tashlang
  }
}

const g = new Graph();
g.qoshQirra("A", "B"); g.qoshQirra("A", "C"); g.qoshQirra("B", "D");

Misol 2 — BFS (eng qisqa yo'l — 2.4, 2.6)

// A dan B gacha eng qisqa yo'l (qadamlar soni — vaznsiz)
function engQisqaYol(graf, boshlanish, manzil) {
  const korilgan = new Set([boshlanish]);
  const queue = [[boshlanish, [boshlanish]]];   // [tugun, yo'l] (3.4)
  let front = 0;
  while (front < queue.length) {
    const [tugun, yol] = queue[front++];
    if (tugun === manzil) return yol;            // topildi — eng qisqa
    for (const qoshni of graf.qoshnilar.get(tugun) || []) {
      if (!korilgan.has(qoshni)) {
        korilgan.add(qoshni);
        queue.push([qoshni, [...yol, qoshni]]);  // yo'lni davom ettirish (2.8)
      }
    }
  }
  return null;   // yo'l yo'q
}
// BFS birinchi topgan yo'l — ENG QISQA (daraja-baraja — 2.4)

Misol 3 — DFS (yo'l bormi, sikl — 2.5, 2.7)

// A dan B gacha yo'l bormi? (rekursiv DFS — 3.11)
function yolBormi(graf, boshlanish, manzil, korilgan = new Set()) {
  if (boshlanish === manzil) return true;
  korilgan.add(boshlanish);
  for (const qoshni of graf.qoshnilar.get(boshlanish) || []) {
    if (!korilgan.has(qoshni)) {
      if (yolBormi(graf, qoshni, manzil, korilgan)) return true;
    }
  }
  return false;
}

Misol 4 — Amaliy: "do'stlar tavsiyasi" (2.4)

// "Do'stning do'stlari" (2-darajadagi tanishlar) — ijtimoiy tarmoq
function tavsiyalar(graf, odam) {
  const dostlar = new Set(graf.qoshnilar.get(odam) || []);
  const tavsiya = new Set();
  for (const dost of dostlar) {
    for (const dostningDosti of graf.qoshnilar.get(dost) || []) {
      // o'zi emas va allaqachon do'st emas (2.9: Set amallari)
      if (dostningDosti !== odam && !dostlar.has(dostningDosti)) {
        tavsiya.add(dostningDosti);
      }
    }
  }
  return [...tavsiya];   // tavsiya etiladigan tanishlar
}

Misol 5 — Dijkstra algoritmi: Vaznli grafda eng arzon yo'l (2.6)

function dijkstra(graf, boshlanish) {
  const masofalar = {};
  const korilgan = new Set();

  for (const tugun in graf) {
    masofalar[tugun] = Infinity;
  }
  masofalar[boshlanish] = 0;

  while (korilgan.size < Object.keys(graf).length) {
    let engYaqin = null;
    let engKichikMasofa = Infinity;

    for (const tugun in masofalar) {
      if (!korilgan.has(tugun) && masofalar[tugun] < engKichikMasofa) {
        engKichikMasofa = masofalar[tugun];
        engYaqin = tugun;
      }
    }

    if (engYaqin === null || engKichikMasofa === Infinity) break;
    korilgan.add(engYaqin);

    for (const { qoshni, vazn } of graf[engYaqin]) {
      const yangiMasofa = masofalar[engYaqin] + vazn;
      if (yangiMasofa < masofalar[qoshni]) {
        masofalar[qoshni] = yangiMasofa;
      }
    }
  }

  return masofalar;
}

// Vaznli yo'naltirilgan graf:
const vaznliGraf = {
  A: [{ qoshni: "B", vazn: 4 }, { qoshni: "C", vazn: 2 }],
  B: [{ qoshni: "D", vazn: 5 }],
  C: [{ qoshni: "B", vazn: 1 }, { qoshni: "D", vazn: 8 }],
  D: []
};

console.log(dijkstra(vaznliGraf, "A"));
// Natija: { A: 0, B: 3, C: 2, D: 8 } (A -> C -> B orqali B ga masofa 3!)

Misol 6 — Topological Sort: Kahn algoritmi (2.7)

function topologicalSort(tugunlar, qirralar) {
  const inDegree = {};
  const graf = {};

  for (const t of tugunlar) {
    inDegree[t] = 0;
    graf[t] = [];
  }

  for (const [u, v] of qirralar) {
    graf[u].push(v);
    inDegree[v]++;
  }

  const queue = [];
  for (const t of tugunlar) {
    if (inDegree[t] === 0) queue.push(t);
  }

  const tartib = [];
  let front = 0;

  while (front < queue.length) {
    const t = queue[front++];
    tartib.push(t);

    for (const qoshni of graf[t]) {
      inDegree[qoshni]--;
      if (inDegree[qoshni] === 0) {
        queue.push(qoshni);
      }
    }
  }

  if (tartib.length !== tugunlar.length) {
    throw new Error("Grafda sikl aniqlandi — topological sort imkonsiz!");
  }

  return tartib;
}

const fanlar = ["Algoritm", "Matematika", "Dasturlash", "Web"];
const bogliqlik = [
  ["Matematika", "Algoritm"],
  ["Dasturlash", "Algoritm"],
  ["Algoritm", "Web"]
];

console.log(topologicalSort(fanlar, bogliqlik));
// ["Matematika", "Dasturlash", "Algoritm", "Web"]

5. To'g'ri va noto'g'ri holatlar

1) korilgan Set'siz traversal

// ❌ sikl bo'lsa — cheksiz tsikl (2.4, 3.4)
function bfs(graf, t) { const q = [t]; while (q.length) { ... q.push(qoshni); } }

// ✅ korilganni belgilash (MAJBURIY)
const korilgan = new Set([t]);
if (!korilgan.has(qoshni)) { korilgan.add(qoshni); q.push(qoshni); }

2) Vaznli grafda BFS (Dijkstra o'rniga)

❌ vaznli (masofa) grafda BFS — eng kam QADAM beradi, eng kam MASOFA emas 2.6-bob
✅ vaznli eng qisqa yo'l → Dijkstra (Heap — 3.8)

3) Noto'g'ri ko'rsatish (matrix vs list)

❌ siyrak (kam qirrali) graf uchun matrix — O(V²) xotira isrofi 2.3-bob
✅ adjacency list — O(V+E)

4) Yo'naltirilgan/yo'naltirilmagan chalkashligi

// undirected — ikki tomonlama qo'shish
this.qoshnilar.get(a).push(b);
this.qoshnilar.get(b).push(a);   // ❗ directed bo'lsa, bu KERAK EMAS (2.2)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Cheksiz tsikl (traversal)

Sababi: korilgan Set yo'q, graf sikli (2.4, 1-holat). Yechimi: ko'rilgan tugunlarni Set'da belgilash.

Xato 2 — Cannot read properties of undefined

Sababi: tugun grafda yo'q (graf[t] undefined). Yechimi: graf.qoshnilar.get(t) || [] 2.1-bob; tugun borligini tekshiring.

Xato 3 — BFS eng qisqa yo'lni topmaydi (vaznli)

Sababi: vaznli grafda BFS 2.6-bob. Yechimi: Dijkstra (vaznli) yoki vaznsiz uchun BFS.

Xato 4 — Katta grafda sekin/xotira

Sababi: matrix zich emas grafda (O(V²) — 2.8) yoki BFS'da shift 3.4-bob. Yechimi: adjacency list; Queue ko'rsatkich bilan 3.4-bob.

Xato 5 — Stack overflow (DFS rekursiya)

Sababi: juda katta/chuqur graf + rekursiv DFS (3.11, 0.1). Yechimi: iterativ DFS (Stack — 3.4).

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Tree 3.6-bob: daraxt — maxsus graf (siklsiz, bir ota).
• Queue/Stack 3.4-bob: BFS — Queue, DFS — Stack.
• Set/Map (2.9, 3.5): adjacency list, korilgan.
• Rekursiya 3.11-bob: rekursiv DFS.
• Heap 3.8-bob: Dijkstra — priority queue.
• Internet/tarmoq 0.4-bob: routing — graf algoritmlari.
• npm/build (0.7, 2.14): bog'liqlik grafi, topological sort, circular dependency.
• Real: ijtimoiy tarmoq, navigatsiya, tavsiya tizimi.

8. Eng yaxshi amaliyotlar (best practices)

• korilgan Set'ni doim ishlating — sikldan saqlaydi (MAJBURIY — 2.4).
• Adjacency list (Map/Object) — ko'p holatda; matrix faqat zich/O(1) tekshiruv 2.3-bob.
• Vaznsiz eng qisqa yo'l → BFS; vaznli → Dijkstra 2.6-bob.
• BFS — Queue (ko'rsatkich bilan, 3.4); DFS — rekursiya yoki Stack (katta grafda iterativ — 6-bo'lim).
• Yo'naltirilgan/yo'naltirilmaganni aniqlang — qirra qo'shishda (2.2, 4-holat).
• || [] bilan mavjud bo'lmagan tugundan himoyalaning 2.1-bob.
• Real muammoni graf sifatida ko'ring — bog'lanishlar bo'lsa, graf algoritmi qo'llaniladi.

9. Amaliy loyiha: "Ijtimoiy Tarmoq Graf Tahlilchisi"

Graf va uning algoritmlarini real masalada qo'llash.

Maqsad

Graf qurish, BFS/DFS yurish va eng qisqa yo'l, tavsiya, sikl aniqlash algoritmlarini amalda mustahkamlash.

Talablar (requirements)

1. Graph class: adjacency list (Map); addVertex, addEdge (yo'naltirilgan va yo'naltirilmagan rejim), neighbors (Misol 1).
2. BFS va DFS: bfs, dfs — korilgan Set bilan; barcha tugunlarni qaytaradi (Misol 2, 3).
3. Eng qisqa yo'l: shortestPath(a, b) — BFS bilan yo'lni qaytaradi (Misol 2).
4. Do'stlar tavsiyasi: recommend(odam) — 2-darajadagi tanishlar (Misol 4).
5. Sikl aniqlash: hasCycle() — DFS bilan 2.7-bob.
6. Bog'langan komponentlar: necha alohida "guruh" bor (bog'lanmagan qismlar).
7. Topological sort (bonus): DAG'da bog'liqlik tartibi 2.7-bob.
8. Vaznli + Dijkstra (bonus): vaznli grafda eng qisqa masofa (2.6, Heap — 3.8).
9. Chegaraviy holatlar: bo'sh graf, bog'lanmagan tugun, yo'l yo'q 0.6-bob.

Maslahatlar (hint)

• Adjacency list: Map<tugun, [qo'shnilar]> 2.9-bob.
• BFS — Queue (ko'rsatkich, 3.4) + korilgan Set; DFS — rekursiya 3.11-bob + Set.
• Eng qisqa yo'l: BFS'da yo'lni ham saqlang ([tugun, yol] — Misol 2).
• korilgan Set'siz — cheksiz tsikl (6-bo'lim).
• Sikl: DFS'da "hozir yo'lda" tugunlarni belgilash.
• Bog'langan komponentlar: ko'rilmagan tugundan yangi BFS/DFS boshlash.

"Tayyor" mezonlari (acceptance criteria)

• Graf qurish (directed/undirected) ishlaydi.
• BFS va DFS barcha tugunlarni to'g'ri yuradi (sikl bo'lsa ham qulamaydi).
• Eng qisqa yo'l BFS bilan to'g'ri.
• Tavsiya 2-darajadagi tanishlarni beradi.
• Sikl aniqlash to'g'ri ishlaydi.
• Bog'langan komponentlar soni to'g'ri.
• korilgan Set ishlatilgan (cheksiz tsikl yo'q).
• Bo'sh/bog'lanmagan/yo'l yo'q holatlar qulamaydi.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda eng umumiy bog'langan tuzilmani — Graphni o'rgandik:

• Graph — vertex (tugun) + edge (qirra); daraxt 3.6-bob — uning maxsus holati.
• Turlari: directed/undirected, weighted, cyclic/acyclic (DAG).
• Ko'rsatish: adjacency list (Map — ko'p holatda) yoki adjacency matrix (zich/O(1) tekshiruv).
• BFS (Queue — daraja-baraja, eng qisqa yo'l vaznsiz) va DFS (Stack/rekursiya — yo'l/sikl). korilgan Set MAJBURIY (sikldan saqlaydi).
• Dijkstra — vaznli eng qisqa yo'l (Heap — 3.8); topological sort — DAG tartibi.
• Real: ijtimoiy tarmoq, navigatsiya, tavsiya, bog'liqlik grafi.

Keyingi bob — 3.8-bob: Heap (priority queue). Queue 3.4-bob FIFO edi; ba'zan element muhimligi bo'yicha chiqishi kerak (kasalxona shoshilinch navbati, Dijkstra). Heap — aynan shu: eng katta/kichik elementni doim O(log n) da beradi. Priority Queue va heap sort 3.9-bob ning asosi.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — graph algoritmlari murakkabligi (BFS/DFS O(V+E))
• Universal CS — graph representation, BFS/DFS, Dijkstra, topological sort
• MDN Web Docs — Map/Set (adjacency list, korilgan — 2.9)