WisarWisar
Dasturlash kitobi/3-QISM — Algoritmlar12 daqiqa

3.7-bob: Graph (graf)

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

text
       (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).
text
  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):

js
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:

text
      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:

text
  A dan boshla:
  Daraja 0: A
  Daraja 1: B, C    (A ning qo'shnilari)
  Daraja 2: D       (B, C ning qo'shnilari)
  Daraja 3: E
js
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):

js
// 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 Dijkstra algoritmi (eng kam vaznli yo'l — masalan eng qisqa masofa). Priority Queue (Heap — 3.8) ishlatadi.
text
  Vaznsiz: A dan E gacha eng kam QADAM (BFS)
  Vaznli:  A dan E gacha eng kam MASOFA/NARX (Dijkstra)

Dijkstra murakkabroq; g'oyasini bilish kifoya (navigatsiya ilovalari shuni ishlatadi).

2.7. Sikl aniqlash va topological sort

  • Sikl aniqlash — grafda davriy bog'liqlik bormi (DFS bilan). Misol: npm paketlar bir-biriga bog'liq (circular dependency — 2.14).
  • Topological sort — DAG'da 2.2-bob bog'liqliklarni tartibga solish: "A B dan oldin bo'lishi kerak". Misol: build tartibi, kurs prerekvizitlari, task rejalashtirish.
text
  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.
text
  (A—B—C)   (D—E)   (F)      3 ta bog'langan komponent
  to'da 1   to'da 2  yolg'iz

2.8. Murakkablik

Amal Adjacency List Adjacency Matrix
BFS / DFS O(V + E) O(V²)
Bog'langanmi? O(degree) O(1)
Xotira O(V + E) O(V²)

V — tugunlar soni, E — qirralar soni.

3. Sintaksis — tez ma'lumotnoma

js
// 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)

js
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 tashla
  }
}

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)

js
// 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 ettir (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)

js
// 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)

js
// "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
}

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

1) korilgan Set'siz traversal

js
//  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)

text
 vaznli (masofa) grafda BFS — eng kam QADAM beradi, eng kam MASOFA emas (2.6)
 vaznli eng qisqa yo'l  Dijkstra (Heap — 3.8)

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

text
 siyrak (kam qirrali) graf uchun matrix — O(V²) xotira isrofi (2.3)
 adjacency list — O(V+E)

4) Yo'naltirilgan/yo'naltirilmagan chalkashligi

js
// undirected — ikki tomonlama qo'sh
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)

Izohlar (0)

Izoh yozish uchun kiring.

  • Hozircha izoh yo'q. Birinchi bo'ling!
3.7-bob: Graph (graf) — Wisar