Graf atamalari va ko'rinishlari: tugun, qirra va xaritani kodda saqlash

Qisqacha: Graf — tugunlar (nuqtalar) va ularni bog'lovchi qirralar (chiziqlar) to'plami. Yo'l xaritasi, do'stlar tarmog'i, paketlar bog'liqligi — hammasi graf. Kodda graf ko'pincha qo'shnilik ro'yxati sifatida saqlanadi: har tugun uchun qo'shnilari ro'yxati (Map). U O(V + E) xotira oladi; qo'shnilik matritsasi esa O(V²) oladi, lekin "ikki tugun bog'langanmi?" degan savolga O(1) da javob beradi.

Bu darsda

• Graf atamalarini tushuntira olasiz: tugun, qirra, qo'shni, daraja, yo'l, sikl.
• Yo'nalgan va yo'nalmagan, vaznli va vaznsiz graflarni farqlay olasiz.
• Qirralar ro'yxatidan qo'shnilik ro'yxatini (Map) va qo'shnilik matritsasini qura olasiz.
• Qaysi ko'rinish qachon yaxshi ekanini Big-O va o'lchov bilan asoslay olasiz.

Oldin bilishingiz kerak: Daraxt atamalari va binar daraxt, Daraxt bo'ylab yurish: DFS va BFS, Map, Xotira murakkabligi.

1. Nega bu kerak?

«Bahor» oshxonasi yetkazib berishni kengaytirdi. Endi kuryer Chilonzor, Olmazor, Yunusobod, Mirobod, Sergeli va Qo'yliqqa boradi. Jasur aka Sardorga vazifa berdi: "Dastur kuryerga eng tez yo'lni aytsin." Sardor o'yladi: buning uchun avval dastur xaritani bilishi kerak. Qaysi mahalladan qaysi mahallaga to'g'ri yo'l bor, u necha daqiqa?

Daraxtlarni o'rgandik (Daraxt atamalari). Daraxtda har tugunning bitta otasi bor va aylanma yo'l yo'q. Shahar xaritasi esa boshqacha. Bahor'dan Sergeli'ga to'g'ri yo'l bor, Chilonzor orqali ham, Mirobod orqali ham borsa bo'ladi. Yo'llar aylanib, yana boshlang'ich joyga qaytadi. Bunday tuzilmani daraxt bilan saqlab bo'lmaydi — bizga graf kerak.

Bu dars — 14-qismdagi graflar bo'limining boshlanishi. Bugun graf atamalarini va uni kodda saqlashni o'rganamiz. Keyingi darslarda shu xaritada yuramiz (BFS va DFS), eng qisqa yo'lni topamiz (Eng qisqa yo'l) va eng arzon tarmoqni quramiz (Minimal skelet daraxti).

2. Graf nima

2.1 Tugun va qirra

Graf (graph) — nuqtalar va ularni juft-juft bog'lovchi chiziqlar to'plami. Nuqtalar tugun (vertex, node) deyiladi, chiziqlar — qirra (edge). Bizning xaritada tugun — mahalla, qirra — ikki mahalla orasidagi to'g'ri yo'l.

Mana «Bahor» yetkazish xaritasi. Doiralar — tugunlar, chiziqlar — qirralar, chiziqdagi son — yo'l necha daqiqa olishi. Bu rasm butun dars davomida kerak bo'ladi:

flowchart LR
  B(("Bahor")) ---|7| C(("Chilonzor"))
  B ---|9| O(("Olmazor"))
  B ---|6| M(("Mirobod"))
  B ---|16| S(("Sergeli"))
  C ---|10| O
  C ---|9| S
  O ---|11| Y(("Yunusobod"))
  Y ---|5| M
  M ---|9| S
  M ---|13| Q(("Qo'yliq"))
  S ---|3| Q

Bu metro sxemasiga o'xshaydi. Bekatlar — tugunlar, ular orasidagi yo'l — qirralar. Sxemada bekatlar orasidagi haqiqiy masofa ko'rinmaydi. Faqat "qaysi bekat qaysi bekat bilan ulangan" degan ma'lumot muhim. Graf ham xuddi shunday: rasmda tugun qayerda turgani ahamiyatsiz, kim kim bilan bog'langani muhim.

Graf hajmi ikki harf bilan aytiladi: V — tugunlar soni (inglizcha "vertices"), E — qirralar soni ("edges"). Bizning xaritada V = 7, E = 11. Algoritmlarning murakkabligi ham shu ikki harf bilan yoziladi: O(V + E), O(V²). Oldingi darslardagi bitta n o'rniga endi ikkita o'lcham bor — O(a + b) darsidagi kabi.

2.2 Qo'shni va daraja

Ikkita so'z bilan boshlaymiz:

• Qo'shni (neighbor) — qirra bilan to'g'ridan-to'g'ri bog'langan tugun. Bahor'ning qo'shnilari: Chilonzor, Olmazor, Mirobod, Sergeli.
• Daraja (degree) — tugundan chiqadigan qirralar soni. Bahor'ning darajasi 4, Qo'yliq'niki 2.

2.3 Darajalar yig'indisi

Bitta foydali qoida bor. Har qirra ikkita tugunni bog'laydi — demak u ikkala tugunning darajasiga bittadan qo'shadi. Shuning uchun hamma darajalar yig'indisi qirralar sonining ikki baravariga teng. Bizning xaritada darajalar: Bahor 4, Chilonzor 3, Olmazor 3, Yunusobod 2, Mirobod 4, Sergeli 4, Qo'yliq 2. Yig'indi — 22, ya'ni 2 × 11.

Bu qoida kodni tekshirishda qo'l keladi: grafni qurdingiz, darajalarni qo'shdingiz, 2E chiqmadi — demak qayerdadir qirra yo'qolgan.

Tekshirib ko'ring: Kichik kafe tarmog'ida 5 ta filial bor va har filial qolgan to'rttasi bilan to'g'ri yo'l orqali bog'langan. Nechta yo'l bor?

2.4 Yo'l, sikl va bog'langanlik

Endi kuryerning harakati uchun uchta so'z:

• Yo'l (path) — qirralar bo'ylab tugundan tugunga ketma-ket o'tish. Bahor → Mirobod → Sergeli — uzunligi 2 bo'lgan yo'l.
• Sikl (cycle) — boshlangan tugunga qaytib keladigan yo'l. Bahor → Chilonzor → Olmazor → Bahor — sikl.
• Bog'langan (connected) graf — har tugundan har tugunga yo'l bor. Bizning xarita bog'langan.

"Sikl" so'zi kursda for sikli ma'nosida ham ishlatiladi. Graflar haqida gapirganda u "aylanma yo'l" degani. Kontekstdan farqi aniq bo'ladi.

Endi daraxtga yangi ko'z bilan qarang. Daraxt — siklsiz va bog'langan graf. Shuning uchun V ta tugunli daraxtda doim V − 1 ta qirra bor. Bizning xaritada 7 ta tugun va 11 ta qirra — 4 ta "ortiqcha" qirra. Aynan shular sikllarni hosil qiladi.

3. Graf turlari

3.1 Yo'nalgan va yo'nalmagan

Bizning xaritada yo'llar ikki tomonlama: Bahor'dan Mirobod'ga borsa bo'ladi, Mirobod'dan Bahor'ga ham. Bunday graf yo'nalmagan (undirected) deyiladi.

Endi boshqa misol. Mirobod'da bir tomonlama ko'cha bor: undan faqat Yunusobod tomonga yurish mumkin. Yoki Instagram'da: siz kimgadir obuna bo'lsangiz, u sizga obuna bo'lishi shart emas. Bu munosabatlarda yo'nalish bor. Yo'nalgan graf (directed graph) — har qirrasi strelka bo'lgan graf: A → B bor bo'lsa ham, B → A bo'lmasligi mumkin. Rasmda qirra o'q bilan chiziladi.

Yo'nalgan grafda daraja ikkiga bo'linadi: kiruvchi daraja (in-degree) — tugunga kiradigan strelkalar soni, chiquvchi daraja (out-degree) — undan chiqadiganlar. Instagram'da kiruvchi daraja — obunachilar soni, chiquvchi — siz obuna bo'lganlar.

Yana bir muhim misol — vazifalar tartibi. "Guruchni yuvish" "osh damlash" dan oldin bo'lishi kerak. Bu ham yo'nalgan qirra. Bunday graflarni Topologik saralash darsida ko'ramiz.

3.2 Vaznli va vaznsiz

Kuryerga "Bahor'dan Sergeli'ga yo'l bor" degan gap yetmaydi. Unga yo'l necha daqiqa ekani kerak. Vaznli graf (weighted graph) — har qirrasiga son biriktirilgan graf. Bu son vazn (weight) deyiladi: masofa, vaqt, narx. Bizning xaritada vazn — daqiqa.

Vaznsiz (unweighted) grafda hamma qirralar teng — faqat "bog'langan yoki yo'q" muhim. Masalan, "do'stlik" munosabati: ikki odam do'st yoki do'st emas.

Bizning xarita — vaznli va yo'nalmagan graf: qirradagi son — daqiqa. Keyingi bo'limdagi vizualda u kodda qadamma-qadam quriladi. U yerda tugun ichidagi harf — mahalla nomining bosh harfi, ostida — to'liq nomi. Bu xarita keyingi darslarda ham ishlatiladi.

3.3 Siyrak va zich

V ta tugunli yo'nalmagan grafda eng ko'pi bilan V × (V − 1) ÷ 2 ta qirra bo'lishi mumkin. Haqiqiy graflarda qirralar odatda bundan ancha kam. Toshkentda minglab chorraha bor, lekin har chorrahadan 3–5 ta ko'cha chiqadi, mingta emas. Bunday graf siyrak (sparse) deyiladi: E taxminan V ga yaqin. Qirralari V² ga yaqin bo'lsa — zich (dense) graf.

Bu farq kodda grafni qanday saqlashni tanlashda hal qiluvchi bo'ladi. Hozir ko'ramiz.

4. Grafni kodda saqlash

4.1 Qirralar ro'yxati

Eng sodda yo'l — har qirrani massivga yozish. Bu qirralar ro'yxati (edge list): [["B", "C", 7], ["B", "O", 9], ...]. Ma'lumot ko'pincha aynan shu shaklda keladi: jadvaldan, fayldan yoki serverdan.

Lekin bu shakl bilan ishlash noqulay. "Bahor'ning qo'shnilari kimlar?" degan savolga javob berish uchun hamma qirralarni ko'rib chiqish kerak — O(E). Kuryer har chorrahada shu savolni beradi. Shuning uchun qirralar ro'yxati odatda boshqa ko'rinishga aylantiriladi.

4.2 Qo'shnilik ro'yxati

Qo'shnilik ro'yxati (adjacency list) — har tugun uchun uning qo'shnilari ro'yxati. JavaScript'da buning eng qulay shakli — Map: kalit — tugun, qiymat — qo'shnilar massivi. Vaznli grafda har qo'shni yonida vazn ham turadi: [qo'shni, daqiqa].

Quyida qirralar ro'yxatidan qo'shnilik ro'yxatini qadamma-qadam quramiz. Har qadamda bitta yo'l qo'shiladi. Pastdagi o'zgaruvchilar paneliga qarang: yo'l ikkala tugun ro'yxatiga yoziladi, chunki graf yo'nalmagan.

Kodni qatorma-qator ko'ramiz:

• const graph = new Map() — bo'sh lug'at. Hali hech qanday tugun yo'q.
• if (!graph.has(a)) graph.set(a, []) — tugun birinchi marta uchrasa, unga bo'sh ro'yxat ochamiz.
• graph.get(a).push([b, minutes]) — a ning ro'yxatiga b qo'shiladi, yonida daqiqa.
• Keyingi qator xuddi shuni teskari tomonga yozadi. Yo'nalgan grafda bu qator bo'lmaydi.

Har qirra uchun ish o'zgarmas: ikkita has, ikkita push. Demak, butun grafni qurish O(E) vaqt oladi. Xotira — O(V + E): Map da V ta kalit va ro'yxatlarda jami 2E ta yozuv.

Natija bilan ishlash oson. Bahor'ning qo'shnilarini sanab chiqamiz:

const graph = new Map([
  ["B", [["C", 7], ["O", 9], ["M", 6], ["S", 16]]],
  ["Q", [["M", 13], ["S", 3]]],
]);

for (const [neighbor, minutes] of graph.get("B")) {
  console.log(`B -> ${neighbor}: ${minutes} daqiqa`);
}
console.log("Qo'yliq darajasi:", graph.get("Q").length);

Konsolda:

B -> C: 7 daqiqa
B -> O: 9 daqiqa
B -> M: 6 daqiqa
B -> S: 16 daqiqa
Qo'yliq darajasi: 2

Bahor'ning qo'shnilarini ko'rish uchun faqat uning o'z ro'yxati aylanildi — 4 ta qadam. Butun xaritadagi 11 ta qirraga tegilmadi. Tugunning qo'shnilarini aylanish O(daraja) vaqt oladi.

4.3 Yo'nalgan qirra

Bir tomonlama ko'chani qo'shish uchun faqat bitta push yetadi. Lekin tugunning o'zi baribir Map da bo'lishi kerak — aks holda "Yunusobod'dan qayerga borsa bo'ladi?" degan savolga undefined qaytadi:

const graph = new Map();
function addOneWay(from, to) {
  if (!graph.has(from)) graph.set(from, []);
  if (!graph.has(to)) graph.set(to, []);
  graph.get(from).push(to); // faqat bir tomonga
}

addOneWay("M", "Y");
console.log(graph.get("M")); // [ 'Y' ]
console.log(graph.get("Y")); // []

Mirobod'dan Yunusobod'ga borsa bo'ladi, teskarisiga — yo'q. graph.get("Y") bo'sh massiv qaytardi, undefined emas. Bo'sh massiv bilan for...of xatosiz ishlaydi, undefined bilan esa TypeError beradi.

4.4 Qo'shnilik matritsasi

Ikkinchi usul — qo'shnilik matritsasi (adjacency matrix): V × V o'lchamli jadval. matrix[i][j] — i-tugundan j-tugunga qirra bo'lsa 1 (yoki vazn), bo'lmasa 0. Jadval ustunlari va qatorlari tugunlar raqami bilan belgilanadi. Shuning uchun avval har tugun nomiga raqam beramiz:

const roads = [["B", "C"], ["B", "O"], ["B", "M"], ["C", "O"]];
const names = ["B", "C", "O", "M"];
const index = new Map(names.map((name, i) => [name, i]));
const matrix = names.map(() => names.map(() => 0));

for (const [a, b] of roads) {
  matrix[index.get(a)][index.get(b)] = 1;
  matrix[index.get(b)][index.get(a)] = 1;
}
for (const [i, row] of matrix.entries()) {
  console.log(names[i], row.join(" "));
}
console.log(matrix[index.get("C")][index.get("O")]); // 1
console.log(matrix[index.get("C")][index.get("M")]); // 0

Konsolda:

B 0 1 1 1
C 1 0 1 0
O 1 1 0 0
M 1 0 0 0
1
0

names.map(() => names.map(() => 0)) — 4 × 4 nollar jadvali. Har yo'l ikki katakka yoziladi: [B][C] va [C][B]. Shuning uchun yo'nalmagan grafning matritsasi simmetrik — diagonal bo'yicha buklasangiz, ikki yarmi ustma-ust tushadi. Yo'nalgan grafda bu shart emas.

Matritsaning kuchli tomoni — "C va O bog'langanmi?" degan savolga bitta katakka qarab javob beradi: O(1). Qo'shnilik ro'yxatida buning uchun C ning ro'yxatini ko'rib chiqish kerak — O(daraja).

Endi Mirobod qatorini ko'ring: 1 0 0 0. Uning bitta qo'shnisi bor, lekin qo'shnilarni topish uchun to'rtta katakni tekshirdik. Million tugunli xaritada har tugun uchun million katak — hatto qo'shnisi uchta bo'lsa ham.

Tekshirib ko'ring: Matritsada matrix[2][2] (diagonaldagi katak) 1 bo'lsa, bu nimani bildiradi? Bizning xaritada bunday bo'lishi mumkinmi?

5. Qaysi biri yaxshi?

5.1 Big-O bo'yicha

Ko'p graf algoritmlari (BFS, DFS, Dijkstra) "har tugunning qo'shnilarini aylanib chiq" degan ishni qiladi. Ro'yxat bilan bu O(V + E), matritsa bilan — O(V²). Siyrak grafda E taxminan V ga yaqin. Demak, ro'yxat chiziqli, matritsa — kvadratik.

Xotira ham shunday. Toshkentning 100 000 chorrahasi uchun matritsa 100 000 × 100 000 = 10 milliard katak — bir katakka bir bayt bo'lsa ham 10 GB. Qo'shnilik ro'yxati esa 100 000 ta kalit va bir necha yuz ming yozuv — bir necha megabayt.

5.2 O'lchov: n ikki baravar oshsa

Nazariyani tekshiramiz. Har ikki usulda siyrak graf (har tugundan 2 ta tasodifiy qirra, E ≈ 2V) quramiz va hamma tugunlarning hamma qo'shnilarini aylanib chiqamiz. O'lchash usuli — Performansni o'lchash darsidagi usul: isitish, 7 o'lchov, mediana. Har V alohida Node jarayonida o'lchanadi — bir jarayondagi oldingi o'lchov keyingisiga ta'sir qilmasin.

Kirishni urug'li generator yasaydi — bir xil "urug'" (boshlang'ich son) bilan har safar bir xil tasodifiy graf chiqaradigan funksiya (Asosiy murakkablik sinflari darsidagi makeRandom kabi). O'lchov dasturi taxminan shunday — o'zingiz ham ishga tushirib ko'ring:

// graf-olchov.mjs — ishga tushirish: node graf-olchov.mjs 8000
const n = Number(process.argv[2]); // tugunlar soni (V)
let seed = 2026; // urug'li generator: har safar bir xil graf
const random = () => (seed = (seed * 16807) % 2147483647);
const edges = Array.from({ length: 2 * n }, // E ≈ 2V
  () => [random() % n, random() % n]);

function walkList() {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  let sum = 0;
  for (let v = 0; v < n; v++) {
    for (const u of adj[v]) sum += u; // hamma qo'shnilar
  }
  return sum; // natija ishlatiladi — o'lik kod bo'lmasin
}

for (let i = 0; i < 20; i++) walkList(); // isitish
const times = [];
for (let i = 0; i < 7; i++) {
  const start = performance.now();
  walkList();
  times.push(performance.now() - start);
}
times.sort((a, b) => a - b);
console.log(`V = ${n}: ≈ ${times[3].toFixed(2)} ms (mediana)`);

process.argv[2] — buyruq qatoridagi birinchi argument (8000). Har V uchun dasturni qaytadan ishga tushiramiz: node graf-olchov.mjs 1000, keyin 2000, 4000 va 8000. Shunda har o'lchov alohida jarayonda bo'ladi. Grafni qurish (edges) o'lchanmaydi, faqat walkList. 7 ta vaqt saralanadi va o'rtadagisi (times[3]) — mediana — olinadi.

Tugunlar bu yerda nom emas, raqam (0 dan n − 1 gacha). Shuning uchun Map o'rniga oddiy massiv ishlatdik: adj[v] — v-tugunning qo'shnilari. Matritsa variantida adj o'rniga Uint8Array(n * n) — har katak bir bayt — va ikki qavatli sikl bilan hamma kataklar ko'riladi.

Natijalar (Node 24.21, taxminan — sizda boshqacha bo'ladi):

8 000 tugunda farq taxminan 40 baravar. Qatorma-qator qarang: matritsa har safar taxminan 4 baravar sekinlashdi (×3,9, ×4,7, ×4,7), ro'yxat — taxminan ikki baravar. Kichik vaqtlarda shovqin ko'p, shuning uchun ro'yxatni kattaroq graflarda ham o'lchadik — matritsa u yerga sig'maydi:

Nisbat ikkidan biroz katta — katta massivlarda protsessor keshi va axlat yig'uvchi qo'shimcha vaqt oladi. Lekin o'sish shakli chiziqli: to'rt baravar emas. 800 000 tugunli matritsa esa 640 milliard bayt bo'lardi — oddiy kompyuterga sig'maydi.

Nimaga qarang: ikkala chiziq ham bir xil nuqtadan boshlanadi, lekin matritsa chizig'i tepaga "uchadi" — kvadratik o'sish. Ro'yxat chizig'i deyarli to'g'ri.

5.3 Qachon matritsa?

Matritsa yomon degani emas. U uch holatda yaxshi:

• Graf zich — har tugun deyarli hamma bilan bog'langan. Unda E ≈ V², va ro'yxat ham O(V²) oladi.
• Graf kichik — 100 ta tugun uchun 10 000 katak. Bu hech narsa emas, kod esa soddaroq.
• "Bog'langanmi?" savoli juda ko'p — har safar O(1) javob kerak.

Qolgan hamma holatda — ayniqsa haqiqiy xarita, ijtimoiy tarmoq, bog'liqliklar uchun — qo'shnilik ro'yxati. Kursning keyingi darslarida asosan shuni ishlatamiz.

Tekshirib ko'ring: «Bahor»ning 6 ta oshpazi bor. Jasur aka har ikki oshpaz birga ishlay oladimi yoki yo'qmi — shuni yozib bormoqchi va jadvaldan tez-tez "Akmal va Nodira birga ishlay oladimi?" deb so'raydi. Qaysi ko'rinish qulay?

6. Chegaraviy holatlar

• Bo'sh graf. Qirralar ro'yxati bo'sh — Map ham bo'sh. Algoritm graph.get("B") qilsa, undefined oladi. Kod buni kutishi kerak.
• Qirrasiz tugun. Yangi Qibray filiali ochildi, lekin hali yo'l yo'q. Qirralar ro'yxatida u umuman ko'rinmaydi! Shuning uchun haqiqiy kodda tugunlar ro'yxati alohida beriladi va har biriga oldindan bo'sh massiv ochiladi.
• Takroriy qirra. Ma'lumotda B–C yo'li ikki marta yozilgan bo'lsa, ro'yxatda C ikki marta paydo bo'ladi. Darajalar noto'g'ri chiqadi. Kerak bo'lsa, qo'shnilarni Set da saqlang.
• Halqa. ["B", "B", 0] kabi qirra — odatda ma'lumot xatosi.
• Yo'nalishni aralashtirish. Yo'nalgan grafda teskari push ni yozib qo'ysangiz, bir tomonlama ko'cha ikki tomonlama bo'lib qoladi — kuryer taqiqlangan yo'ldan yuradi.

7. Ko'p uchraydigan xatolar

7.1 Ikkinchi push ni unutish

Yo'nalmagan grafda faqat graph.get(a).push(b) yozilsa, B'dan A'ga yo'l "yo'qoladi". Belgisi: darajalar yig'indisi 2E emas, E chiqadi. Tuzatish: har qirrani ikkala tomonga yozing yoki addRoad funksiyasini bitta joyda yozib, hamma joyda shuni ishlating.

7.2 Mavjud bo'lmagan tugun

const graph = new Map([["B", ["C"]]]);
for (const neighbor of graph.get("Q")) console.log(neighbor);

TypeError: graph.get is not a function or its return value is not iterable

Tarjimasi: "graph.get funksiya emas yoki uning qaytargan qiymatini aylanib bo'lmaydi". Node ikki ehtimolni birga aytadi. Bu yerda ikkinchisi: Map da "Q" kaliti yo'q, get undefined qaytardi, for...of esa undefined ni aylana olmaydi. Tuzatish: grafga hamma tugunni oldindan qo'shing yoki graph.get(v) ?? [] yozing.

7.3 Katta siyrak graf uchun matritsa

"Matritsa sodda" deb 50 000 tugunli xaritaga Array(50000) ichida Array(50000) yasash — 2,5 milliard katak. Node xotira yetmay yiqiladi. Tuzatish: V katta va E kichik bo'lsa — qo'shnilik ro'yxati.

7.4 Rasmni graf deb o'ylash

Tugunlarning rasmdagi joyi (x, y) grafning bir qismi emas. Ikkita qirra rasmda kesishsa ham, ular chorrahada uchrashmaydi — agar u yerda tugun bo'lmasa. Tuzatish: grafni rasm bilan emas, qirralar ro'yxati bilan tekshiring.

8. Mashqlar

1-mashq (oson): Darajalarni sanang

Darsdagi xarita uchun: (a) eng katta darajali tugunlar qaysilar? (b) Qo'yliq'dan Olmazor'ga eng kam qirrali yo'l nechta qirradan iborat? (c) Xaritaga Yunusobod–Qo'yliq yo'li qo'shilsa, darajalar yig'indisi nechaga teng bo'ladi?

2-mashq (o'rta): Matritsadan ro'yxatga

matrixToList(names, matrix) funksiyasini yozing: u qo'shnilik matritsasini qo'shnilik ro'yxatiga (Map) aylantirsin. Ishora: ikki qavatli sikl kerak, matrix[i][j] === 1 bo'lsa names[j] ni names[i] ning ro'yxatiga qo'shing. Funksiyaning murakkabligi qanday?

function matrixToList(names, matrix) {
  const graph = new Map();
  for (let i = 0; i < names.length; i++) {
    const neighbors = [];
    for (let j = 0; j < names.length; j++) {
      if (matrix[i][j] === 1) neighbors.push(names[j]);
    }
    graph.set(names[i], neighbors);
  }
  return graph;
}

const names = ["B", "C", "O", "M"];
const matrix = [
  [0, 1, 1, 1],
  [1, 0, 1, 0],
  [1, 1, 0, 0],
  [1, 0, 0, 0],
];
console.log(matrixToList(names, matrix));

Map(4) {
  'B' => [ 'C', 'O', 'M' ],
  'C' => [ 'B', 'O' ],
  'O' => [ 'B', 'C' ],
  'M' => [ 'B' ]
}

3-mashq (qiyin): Graf quruvchi va testlar

kurs/mashqlar/14/45-graf/graf.test.mjs faylida buildGraph(edges, directed = false) funksiyasini yozing. U qirralar ro'yxatidan qo'shnilik ro'yxatini (Map) qursin; directed true bo'lsa — faqat bir tomonga yozsin. To'rtta test (node:test):

1. Bo'sh ro'yxat — bo'sh graf.
2. Yo'nalmagan: B–C qirrasi ikkala ro'yxatda.
3. Yo'nalgan: B → C bor, C ning ro'yxati bo'sh (lekin tugun mavjud).
4. Darajalar yig'indisi = 2 × qirralar soni.

// kurs/mashqlar/14/45-graf/graf.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function buildGraph(edges, directed = false) {
  const graph = new Map();
  for (const [a, b] of edges) {
    if (!graph.has(a)) graph.set(a, []);
    if (!graph.has(b)) graph.set(b, []);
    graph.get(a).push(b);
    if (!directed) graph.get(b).push(a);
  }
  return graph;
}

test("bo'sh ro'yxat — bo'sh graf", () => {
  assert.equal(buildGraph([]).size, 0);
});

test("yo'nalmagan — ikki tomonga yoziladi", () => {
  const g = buildGraph([["B", "C"]]);
  assert.deepEqual(g.get("B"), ["C"]);
  assert.deepEqual(g.get("C"), ["B"]);
});

test("yo'nalgan — faqat bir tomonga", () => {
  const g = buildGraph([["B", "C"]], true);
  assert.deepEqual(g.get("B"), ["C"]);
  assert.deepEqual(g.get("C"), []); // tugun bor, qo'shnisi yo'q
});

test("darajalar yig'indisi = 2 × qirralar", () => {
  const roads = [["B", "C"], ["B", "O"], ["B", "M"], ["C", "O"]];
  const g = buildGraph(roads);
  let sum = 0;
  for (const list of g.values()) sum += list.length;
  assert.equal(sum, 2 * roads.length);
});

✔ bo'sh ro'yxat — bo'sh graf (0.7526ms)
✔ yo'nalmagan — ikki tomonga yoziladi (0.6669ms)
✔ yo'nalgan — faqat bir tomonga (0.1202ms)
✔ darajalar yig'indisi = 2 × qirralar (0.128ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 80.2776

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md jadvaliga graflar uchun qatorlar qo'shing: qirralar ro'yxatidan qo'shnilik ro'yxatini qurish, qo'shnilik matritsasini qurish, "A va B bog'langanmi?" (ikkala ko'rinishda), "A ning qo'shnilari" (ikkala ko'rinishda). Jadval tepasiga bir qator izoh yozing: graflarda n o'rniga V va E ishlatiladi.

> Graflarda: V — tugunlar soni, E — qirralar soni, d — tugun darajasi.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Grafni qurish | qo'shnilik ro'yxati (Map) | O(V + E) | O(V + E) |
| Grafni qurish | qo'shnilik matritsasi | O(V²) | O(V²) |
| A–B bog'langanmi? | ro'yxat | O(d) | O(1) |
| A–B bog'langanmi? | matritsa | O(1) | O(1) |
| A ning qo'shnilari | ro'yxat | O(d) | O(1) |
| A ning qo'shnilari | matritsa | O(V) | O(1) |

git add 14/MURAKKABLIK.md 14/45-graf
git commit -m "14/45: graf ko'rinishlari — jadval va buildGraph testlari"

9. Real ishda

• Xaritalar va yetkazish. Navigatsiya ilovalari va taksi xizmatlari shahar ko'chalarini vaznli yo'nalgan graf sifatida saqlaydi: chorraha — tugun, ko'cha — qirra, vazn — vaqt. Bir tomonlama ko'chalar — yo'nalgan qirralar.
• Ijtimoiy tarmoqlar. "Do'stlar" — yo'nalmagan graf, "obunachilar" — yo'nalgan. "Sizga tanish bo'lishi mumkin" tavsiyasi — do'stlaringizning do'stlari, ya'ni ikki qirra uzoqlikdagi tugunlar.
• Bog'liqliklar. package.json dagi paketlar va ularning paketlari — yo'nalgan graf. npm uni har npm install da quradi (npm darsida birinchi qadamini ko'rgansiz; paket menejerlari 16-qismda chuqur). Git'dagi commitlar ham graf: har commit o'z ota commitiga strelka.
• Ma'lumotlar bazasi. Jadvallar orasidagi bog'lanishlar (foydalanuvchi → buyurtma → taom) ham graf; graf bazalari (masalan, Neo4j) aynan shu shaklda saqlaydi.
• Intervyu. Graf masalasini yechishdan oldin "Graf yo'nalganmi? Vaznlimi? Qanchalik katta?" deb so'rash — yaxshi nomzod belgisi. Javobga qarab ko'rinishni tanlaysiz.

Xulosa

• Graf — tugunlar (V) va qirralar (E). Daraxt — siklsiz bog'langan graf, unda E = V − 1.
• Qirralar yo'nalgan (obuna, bir tomonlama ko'cha) yoki yo'nalmagan (ikki tomonlama yo'l), vaznli (daqiqa, narx) yoki vaznsiz bo'ladi.
• Darajalar yig'indisi = 2E — graf to'g'ri qurilganini tekshirish uchun qulay qoida.
• Qo'shnilik ro'yxati (Map) — O(V + E) xotira, qo'shnilarni aylanish O(daraja). Ko'p algoritm uchun asosiy tanlov.
• Matritsa — O(V²) xotira, "bog'langanmi?" O(1). O'lchovda V ikki baravar oshganda matritsa ≈ 4 baravar, ro'yxat ≈ 2 baravar sekinlashdi.

Keyingi dars: Graflarda BFS va DFS — xaritada qatlam-qatlam (BFS) va chuqurlikka (DFS) yurish, visited to'plami va orollar sonini topish.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 20-bob (graflarni ifodalash).
• Robert Sedgewick, Kevin Wayne, "Algorithms", 4-nashr, Addison-Wesley, 2011 — 4.1 (yo'nalmagan graflar), 4.2 (yo'nalgan graflar).
• MDN: Map — developer.mozilla.org