Graflar

Tasavvur qiling, bir shahardan boshqa shaharga borish yo‘lini topmoqchisiz. Faqat shaharlar ro‘yxati yetarli emas: qaysi shaharlar orasida yo‘l borligini, yo‘l bir tomonlamami yoki ikki tomonlamami, masofasi qancha ekanini ham bilish kerak.

Toshkent ───── Samarqand
    │              │
    │              │
 Farg‘ona ───── Buxoro

Bu yerda shaharlar alohida obyektlar, chiziqlar esa ular orasidagi aloqalar. Graph — obyektlar va ular orasidagi munosabatlarni ifodalovchi ma’lumotlar tuzilmasi. O‘zbekcha matnda uni graf deb ataymiz.

Graf faqat xarita uchun emas. Ijtimoiy tarmoqdagi foydalanuvchilar va do‘stliklar, internetdagi sahifalar va havolalar, dastur modullari va dependency’lar, aeroportlar va reyslar, kompyuterlar va tarmoq ulanishlari ham graf ko‘rinishida modellashtirilishi mumkin.

Grafning asosiy kuchi shundaki, ma’lumotlarni faqat ketma-ket yoki daraxtsimon emas, ixtiyoriy bog‘lanishlar bilan ifodalaydi. Buning evaziga graf bilan ishlash array yoki linked listga qaraganda murakkabroq: bir node’ga ko‘p yo‘l orqali yetish, sikl ichida aylanib qolish va eng yaxshi yo‘lni turli mezonlarda izlash mumkin.

Shaharlar xaritasi analogiyasi

Grafni xarita deb tasavvur qilsak:

shahar — vertex, ya’ni uch;
ikki shahar orasidagi yo‘l — edge, ya’ni qirra;
yo‘l masofasi — qirra og‘irligi;
bir tomonlama ko‘cha — yo‘naltirilgan qirra;
bir nechta yo‘ldan tashkil topgan safar — path, ya’ni yo‘l;
boshlagan shaharga qaytib keluvchi yo‘l — cycle, ya’ni sikl.

          80 km
    A ─────────── B
    │             │
30km│             │45km
    │             │
    C ─────────── D
          60 km

Analogiyaning muhim chegarasi bor: grafdagi vertex xotirada rasmda turgan joyida saqlanmaydi. Diagrammadagi masofa ko‘pincha hech narsani anglatmaydi; faqat qirralar va ularga biriktirilgan ma’lumot muhim. Graf xotirada arraylar, ro‘yxatlar, matritsa yoki hash table’lar orqali ifodalanadi.

Asosiy terminlar

Vertex va node

Vertex — grafdagi bitta obyekt. Ko‘p manbalarda node so‘zi ham ishlatiladi. Masalan, ijtimoiy tarmoq grafida har bir foydalanuvchi vertex bo‘lishi mumkin.

Vertex odatda identifikator va foydali ma’lumotga ega:

vertex id: user_42
data: ism, profil, holat

Edge

Edge — ikki vertex orasidagi munosabat. Do‘stlik, reys, yo‘l yoki “modul boshqa modulga bog‘liq” munosabati edge bilan ifodalanadi.

A ─── B        A va B orasida edge bor

Neighbor

Edge orqali bevosita bog‘langan vertexlar qo‘shni (neighbor) deyiladi. A dan B ga edge bo‘lsa, yo‘nalish qoidasiga qarab B Aning qo‘shnisi hisoblanadi.

Degree

Undirected grafda vertexga ulangan qirralar soni uning darajasi (degree):

    B
    │
C ─ A ─ D

degree(A) = 3

Directed grafda ikki tushuncha ajratiladi:

in-degree — vertexga kiruvchi qirralar soni;
out-degree — vertexdan chiquvchi qirralar soni.

Path

Path — qirralar orqali ketma-ket bog‘langan vertexlar yo‘li:

A → C → D → F

Path length vazifaga qarab qirralar soni yoki og‘irliklar yig‘indisini anglatishi mumkin. “Eng qisqa yo‘l” deyilganda qaysi o‘lchov ishlatilayotganini aniqlash kerak.

Cycle

Boshlang‘ich vertexga qirralar orqali qaytib keladigan yopiq yo‘l sikl (cycle) deyiladi:

A → B → C
↑       │
└───────┘

Directed va undirected graflarda cycle aniqlash qoidalari farq qiladi. Undirected grafda ota vertexga qaytuvchi o‘sha qirrani sikl deb xato hisoblamaslik kerak.

Connected component

Undirected grafning bir-biriga path orqali yetib borish mumkin bo‘lgan maksimal vertexlar guruhi bog‘langan komponent (connected component) deyiladi:

A ─ B     C ─ D ─ E      F

3 ta component

Order va size

Graf nazariyasida ba’zan:

graph order — vertexlar soni;
graph size — qirralar soni

deyiladi. DSA murakkabligida vertexlar sonini V, qirralar sonini E bilan belgilaymiz.

Graf turlari

Graf bir vaqtning o‘zida bir nechta xususiyatga ega bo‘lishi mumkin. Masalan, directed, weighted va cyclic graf. Bu turlar bir-birini har doim inkor qilmaydi.

Undirected graph

Yo‘naltirilmagan graf (undirected graph)da qirra ikki tomonga aloqani bildiradi:

A ─── B

A B bilan bog‘langan bo‘lsa, B ham A bilan bog‘langan. Ijtimoiy tarmoqdagi o‘zaro do‘stlik, ikki tomonlama yo‘l yoki bir xil lokal tarmoqdagi to‘g‘ridan-to‘g‘ri ulanish shunday model bo‘lishi mumkin.

Xotirada adjacency list ishlatilsa, bitta mantiqiy edge odatda ikki yozuv bilan saqlanadi:

A: [B]
B: [A]

Bu qirralar sonini hisoblashda muhim: adjacency yozuvlarini sanab ikki ga bo‘lish talab qilinishi mumkin. Self-loop bilan bog‘liq aniq hisob konvensiyaga bog‘liq.

Directed graph

Yo‘naltirilgan graf (directed graph)da edge yo‘nalishga ega:

A → B

Adan Bga borish mumkinligi Bdan Aga ham borish mumkinligini anglatmaydi. Instagramdagi “follow”, web sahifadagi hyperlink, prerequisite va bir tomonlama ko‘cha directed munosabatdir.

A → B → C
    ↑
    D

Bu grafda Bning in-degree’i 2, out-degree’i 1.

Weighted graph

Og‘irlikli graf (weighted graph)da har edge sonli qiymat saqlaydi:

A ──5── B ──2── C
 \             /
  └────10─────┘

Og‘irlik masofa, vaqt, narx, sig‘im, risk yoki boshqa mezon bo‘lishi mumkin. Eng kam qirralar soniga ega path eng kichik og‘irlik yig‘indisiga ega path bo‘lishi shart emas.

Masalan, A → C bitta qirra va og‘irligi 10; A → B → C ikkita qirra, ammo jami 7. Transport marshrutida ikkinchisi arzonroq yoki qisqaroq bo‘lishi mumkin.

Manfiy og‘irliklar ham ayrim modellarda mavjud, lekin barcha shortest-path algoritmlari ular bilan ishlamaydi. Dijkstra manfiy edge mavjud graf uchun umumiy holda to‘g‘ri emas.

Unweighted graph

Og‘irliksiz graf (unweighted graph)da qirralar alohida qiymatga ega emas yoki barchasi teng deb olinadi. Eng qisqa yo‘l qirralar soni bo‘yicha o‘lchanadi. BFS bunday grafda eng kam qirrali pathni topadi.

Cyclic va acyclic graph

Cycle mavjud graf cyclic, cycle yo‘q graf acyclic deyiladi. Directed acyclic graph qisqacha DAG:

A → B → D
 \      ↑
  → C ──┘

DAG dependency, build bosqichlari, dars prerequisite’lari va versiyalar ketma-ketligini ifodalashda ishlatiladi. Unda topological ordering mavjud. Agar dependency cycle bo‘lsa, qaysi vazifani avval bajarish muammosi kelib chiqadi.

Connected va disconnected graph

Undirected grafda har bir vertexdan istalgan boshqa vertexga path bo‘lsa, graf connected. Aks holda u disconnected va bir nechta componentga ega.

Directed grafda connectedlik nozikroq:

strongly connected — har bir vertexdan boshqasiga yo‘nalishlarga rioya qilib yetish mumkin;
weakly connected — yo‘nalishlar e’tiborsiz qoldirilsa graf connected.

Simple graph, self-loop va parallel edge

Simple graph odatda self-loop va bir juft vertex orasidagi parallel edge’larsiz graf:

Self-loop:      A ↺

Parallel edge:  A ═══ B

Real transport grafida ikki shahar orasidagi bir nechta reys parallel edge bo‘lishi mumkin. Ijtimoiy do‘stlik grafida esa bitta juftlik uchun bir edge yetarli. Ma’lumot modeli edge’larni takrorlashga ruxsat beradimi, oldindan aniqlanadi.

Sparse va dense graph

Vertexlar soniga nisbatan qirralar kam bo‘lsa graf sparse, qirralar maksimal songa yaqin bo‘lsa dense.

Undirected simple grafda maksimal edge soni:

V × (V - 1) / 2

Directed simple grafda self-looplarsiz maksimal edge:

V × (V - 1)

Bu farq representation tanlashga ta’sir qiladi: sparse graf uchun adjacency list, dense graf yoki tez edge lookup uchun adjacency matrix ko‘pincha mosroq.

Tree va graph bir xil emas

Tree — grafning maxsus turi. Klassik undirected tree:

connected;
cycle’siz;
V vertex uchun V - 1 edge’ga ega;
istalgan ikki vertex orasida yagona simple path mavjud.

Tree:               Oddiy graph:

    A                    A ─ B
   / \                   │ ╲ │
  B   C                  C ─ D
     /                   cycle bor
    D

Rooted tree’da parent-child iyerarxiyasi bor. Umumiy grafda root, parent yoki “yuqori-past” tushunchasi tabiiy ravishda mavjud emas. Traversal algoritmi vaqtincha parent va traversal tree yaratishi mumkin, lekin bu grafning o‘zi tree degani emas.

Graf xotirada qanday saqlanadi?

Diagramma faqat tushuntirish uchun. Algoritmga vertexning qo‘shnilarini topish va edge mavjudligini tekshirish uchun aniq representation kerak. Eng keng tarqalgan usullar:

edge list;
adjacency list;
adjacency matrix.

Edge list

Har bir qirra vertexlar juftligi sifatida saqlanadi:

Vertices: [A, B, C, D]
Edges:
    (A, B)
    (A, C)
    (B, D)
    (C, D)

Weighted grafda:

(A, B, 5)
(A, C, 2)

Edge list sodda, ixcham va barcha qirralarni ketma-ket ko‘radigan Kruskal kabi algoritmlarda qulay. Ammo Aning barcha qo‘shnisini topish uchun butun E qirrani tekshirish O(E) bo‘lishi mumkin. Muayyan edge mavjudligini tekshirish ham oddiy listda O(E).

Xotira O(V + E) yoki vertex ma’lumotlari alohida bo‘lsa qirralar uchun O(E).

Adjacency list

Har vertex uchun uning qo‘shnilari ro‘yxati saqlanadi:

Graf:
A ─ B
│   │
C ─ D

Adjacency list:
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Weighted variantda qo‘shni bilan birga og‘irlik turadi:

A: [(B, 5), (C, 2)]

Vertexlar zich 0..V-1 indexlarda bo‘lsa, tashqi tuzilma array bo‘lishi mumkin. IDlar string yoki siyrak bo‘lsa, hash map ishlatilishi mumkin:

vertex_id → neighbors collection

Adjacency list xotirasi O(V + E). Undirected grafda har edge ikki ro‘yxatda bo‘lsa ham, 2E Big O’da O(E). Vertex qo‘shnilarini olish O(degree(v)); u-v edge mavjudligini oddiy neighbor listda O(degree(u)) tekshirish kerak. Neighbor kolleksiyasi hash set bo‘lsa kutiladigan lookup tezlashadi, lekin qo‘shimcha xotira sarflanadi.

Sparse graflar va barcha qo‘shnilarni traversal qilish uchun adjacency list ko‘pincha eng yaxshi umumiy tanlov.

Adjacency matrix

V × V o‘lchamli matrix ishlatiladi. matrix[u][v] edge borligini yoki uning og‘irligini bildiradi:

      A  B  C  D
   +------------
A  | 0  1  1  0
B  | 1  0  0  1
C  | 1  0  0  1
D  | 0  1  1  0

Undirected graf matrixi bosh diagonalga nisbatan simmetrik. Directed grafda matrix[u][v] bilan matrix[v][u] mustaqil.

Afzalligi:

u → v edge mavjudligini O(1) tekshirish;
edge qo‘shish va o‘chirish O(1);
dense grafda sodda va cache uchun qulay bo‘lishi mumkin.

Cheklovi:

edge juda kam bo‘lsa ham O(V²) xotira;
bitta vertex qo‘shish uchun matrixni kattalashtirish va ko‘chirish O(V²) bo‘lishi mumkin;
uning barcha qo‘shnisini topish uchun butun qatorni O(V) ko‘rish kerak.

Representation taqqoslanishi

Amal/xususiyat	Edge list	Adjacency list	Adjacency matrix
Xotira	`O(V+E)`	`O(V+E)`	`O(V²)`
Edge mavjudligini tekshirish	`O(E)`	`O(degree(u))`	`O(1)`
Barcha neighborlarni olish	`O(E)`	`O(degree(u))`	`O(V)`
Edge qo‘shish	odatda `O(1)`	odatda `O(1)`	`O(1)`
Edge o‘chirish	`O(E)`	`O(degree(u))`	`O(1)`
Sparse graf	mos	juda mos	xotira isrof qiladi
Dense graf	ayrim algoritmlarda	mumkin	ko‘pincha mos

Jadval klassik array/list implementatsiyalarini nazarda tutadi. Hash set, sorted list yoki maxsus siqilgan matrix ishlatilsa murakkabliklar o‘zgarishi mumkin.

Asosiy amallar

Quyidagi misollarda adjacency list ishlatiladi.

Bo‘sh graf yaratish

FUNCTION CREATE_GRAPH(directed)
    graph.adjacency = bo‘sh map
    graph.directed = directed
    RETURN graph

Boshqaruv tuzilmasi O(1) vaqt va xotira. Oldindan V vertex uchun array ajratilsa O(V).

Vertex qo‘shish

FUNCTION ADD_VERTEX(graph, vertex)
    IF vertex graph.adjacency ichida mavjud bo‘lmasa
        graph.adjacency[vertex] = bo‘sh neighbor collection

Hash map asosida kutiladigan vaqt O(1). Matrixda yangi vertex qo‘shish qator va ustunni kengaytirish sabab O(V²)gacha borishi mumkin.

Edge qo‘shish

FUNCTION ADD_EDGE(graph, u, v)
    graph.adjacency[u] ga v ni qo‘sh

    IF graph directed bo‘lmasa
        graph.adjacency[v] ga u ni qo‘sh

List oxiriga qo‘shish odatda O(1). Takroriy edge’ni oldini olish kerak bo‘lsa, avval mavjudlikni tekshirish O(degree(u)); neighbor hash set bilan kutiladigan O(1) bo‘lishi mumkin.

Undirected grafda faqat bir yo‘nalishni qo‘shish representationni buzadi: traversal udan vga o‘tadi, vdan uga esa o‘ta olmaydi.

Edge qidirish

Adjacency listda uning qo‘shnilari ko‘riladi:

FUNCTION HAS_EDGE(graph, u, v)
    FOR har bir neighbor graph.adjacency[u] ichida
        IF neighbor = v
            RETURN TRUE

    RETURN FALSE

Vaqt O(degree(u)), matrixda O(1). Weighted grafda topilgan edge yozuvidan weight olinadi.

Edge o‘chirish

FUNCTION REMOVE_EDGE(graph, u, v)
    graph.adjacency[u] dan v ni o‘chir

    IF graph directed bo‘lmasa
        graph.adjacency[v] dan u ni o‘chir

Oddiy listda qidirish va siljitish O(degree(u) + degree(v)) bo‘lishi mumkin. Linked list, hash set yoki boshqa neighbor container tanlovi aniq xarajatni o‘zgartiradi.

Vertex o‘chirish

Vertexni o‘chirish faqat uning ro‘yxatini olib tashlash emas; unga kiruvchi barcha edge ham yo‘qotilishi kerak. Undirected adjacency listda vertex qo‘shnilarining ro‘yxatlaridan ham o‘chiriladi. Directed graf faqat outgoing ro‘yxat saqlasa, incoming edge’larni topish uchun barcha adjacency listlarni ko‘rish O(V + E) bo‘lishi mumkin.

Incoming va outgoing ro‘yxatlarni alohida saqlash o‘chirishni tezlashtiradi, ammo har o‘zgarishda ikkala representationni izchil yangilash va qo‘shimcha xotira talab qiladi.

Qiymat yangilash

Vertex IDdan vertex obyektiga map mavjud bo‘lsa, ma’lumot maydonini yangilash kutiladigan O(1). Vertexning IDsi adjacency kaliti sifatida ishlatilsa, uni o‘zgartirish barcha tegishli edge yozuvlarini yangilashni talab qilishi mumkin. Shu sababli barqaror ID va alohida mutable data ishlatish qulay.

Graf traversal nima?

Traversal — boshlang‘ich vertexdan reachable vertexlarni sistematik ko‘rib chiqish. Arraydan farqli ravishda grafda “keyingi element” yagona emas: bir vertexning bir nechta qo‘shnisi bo‘lishi mumkin.

Cycle sababli tashrif buyurilgan vertexlarni kuzatish zarur:

A → B → C
↑       │
└───────┘

visited bo‘lmasa traversal A, B, C, A, B, C... bo‘lib cheksiz davom etadi.

Ikki asosiy yondashuv:

BFS — qatlamma-qatlam, queue bilan;
DFS — bir yo‘l bo‘ylab chuqur, stack yoki rekursiya bilan.

Breadth-first search

BFS (breadth-first search) boshlang‘ich vertexdan masofa qatlamlari bo‘yicha yuradi. Avval bevosita qo‘shnilar, keyin ularning hali ko‘rilmagan qo‘shnilari qayta ishlanadi.

        A
      /   \
     B     C
    / \     \
   D   E     F

BFS: A, B, C, D, E, F

Queue FIFO tartibi sababli oldin topilgan qatlam keyingi qatlamdan oldin chiqadi.

FUNCTION BFS(graph, start)
    IF start grafda mavjud bo‘lmasa
        RETURN

    queue = bo‘sh queue
    visited = bo‘sh set

    visited ga start ni qo‘sh
    queue.ENQUEUE(start)

    WHILE queue bo‘sh emas
        current = queue.DEQUEUE()
        VISIT current

        FOR har bir neighbor graph.adjacency[current] ichida
            IF neighbor visited ichida bo‘lmasa
                visited ga neighbor ni qo‘sh
                queue.ENQUEUE(neighbor)

Nega enqueue paytida visited qilinadi?

Agar vertex faqat dequeue paytida visited qilinsa, bir nechta parent uni queuega takroran qo‘shishi mumkin:

    A
   / \
  B   C
   \ /
    D

B va C ikkalasi ham Dni enqueue qilishi mumkin. Enqueue qilingan zahoti visited belgilash buni oldini oladi.

BFS dry run

Yuqoridagi graf uchun:

Queue          Olingan       Yangi qo‘shilgan
[A]            A             B, C
[B, C]         B             D
[C, D]         C             hech narsa (D visited)
[D]            D             hech narsa
[]

Traversal tartibi neighborlar kolleksiyasining tartibiga bog‘liq. B va C o‘rni almashishi mumkin, lekin qatlamlar xususiyati saqlanadi.

BFS murakkabligi

Adjacency listda har vertex bir marta queuega kiradi va har edge tegishli ro‘yxatda ko‘riladi:

Vaqt: O(V + E)
Xotira: O(V)

Undirected grafda edge ikki adjacency yozuvida ko‘riladi, 2E esa Big O’da O(E). Adjacency matrixda har olingan vertex uchun butun V qator tekshiriladi, vaqt O(V²).

Og‘irliksiz grafda BFS boshlang‘ich vertexdan eng kam qirrali pathni topadi. Buning uchun har vertexning parent qiymati saqlanib, maqsaddan startgacha teskari yuriladi.

Depth-first search

DFS (depth-first search) bir yo‘l bo‘ylab imkon qadar chuqur boradi, keyin orqaga qaytib boshqa yo‘lni tekshiradi.

        A
      /   \
     B     C
    / \     \
   D   E     F

Mumkin DFS: A, B, D, E, C, F

DFS rekursiya yoki explicit stack bilan yoziladi.

Rekursiv DFS

FUNCTION DFS_RECURSIVE(graph, current, visited)
    visited ga current ni qo‘sh
    VISIT current

    FOR har bir neighbor graph.adjacency[current] ichida
        IF neighbor visited ichida bo‘lmasa
            DFS_RECURSIVE(graph, neighbor, visited)

Har chaqiruv joriy vertex holatini call stackda saqlaydi. Juda chuqur graf stack overflowga olib kelishi mumkin.

Iterativ DFS

FUNCTION DFS_ITERATIVE(graph, start)
    stack = bo‘sh stack
    visited = bo‘sh set
    stack.PUSH(start)

    WHILE stack bo‘sh emas
        current = stack.POP()

        IF current visited ichida bo‘lsa
            CONTINUE

        visited ga current ni qo‘sh
        VISIT current

        FOR har bir neighbor graph.adjacency[current] ichida
            IF neighbor visited ichida bo‘lmasa
                stack.PUSH(neighbor)

Visited enqueue/push vaqtida yoki pop vaqtida boshqarilishi mumkin, lekin duplicate va traversal semantikasi hisobga olinishi kerak. Rekursiv va iterativ DFS neighborlarni qaysi tartibda stackka qo‘yishiga qarab turli, ammo to‘g‘ri traversal tartibini berishi mumkin.

DFS murakkabligi

Adjacency list bilan:

Vaqt: O(V + E)
Xotira: O(V)

Xotira visited va maksimal stack/rekursiya chuqurligini o‘z ichiga oladi. Adjacency matrix bilan vaqt O(V²).

DFS cycle detection, connected component, topological sort, labirint, path mavjudligi va backtrackingda keng ishlatiladi. U og‘irliksiz grafda topgan birinchi path eng qisqa bo‘lishini kafolatlamaydi.

Disconnected grafni to‘liq traversal qilish

Bitta startdan BFS yoki DFS faqat undan reachable vertexlarni ko‘radi. Barcha componentlarni qamrab olish uchun har vertexdan hali visited bo‘lmagan traversal boshlanadi:

FUNCTION TRAVERSE_ALL(graph)
    visited = bo‘sh set

    FOR har bir vertex graph ichida
        IF vertex visited ichida bo‘lmasa
            DFS_RECURSIVE(graph, vertex, visited)

Har yangi boshlanish bitta componentni ochadi. Boshlanishlar sonini sanash undirected grafdagi connected componentlar sonini beradi. Umumiy vaqt baribir O(V + E), chunki har vertex va edge jami bir marta ko‘riladi.

BFS va DFS taqqoslanishi

Xususiyat	BFS	DFS
Asosiy tuzilma	Queue	Stack yoki call stack
Yurish usuli	Qatlamma-qatlam	Chuqurlashib, keyin qaytadi
Unweighted shortest path	Kafolatlaydi	Kafolatlamaydi
Xotira	Keng qatlamda katta bo‘lishi mumkin	Chuqur yo‘lda katta bo‘lishi mumkin
Tabiiy qo‘llanish	Masofa qatlamlari, eng kam qirra	Cycle, component, topological g‘oyalar
Adjacency list vaqti	`O(V+E)`	`O(V+E)`

Ikkalasining Big O vaqti bir xil bo‘lishi mumkin, lekin topilgan path, traversal tartibi va maksimal xotira shakli farq qiladi.

Keng tarqalgan graf algoritmlari

Bu bo‘lim ularning vazifasini ajratadi; har birining to‘liq implementatsiyasi alohida mavzu.

Shortest path

BFS — og‘irliksiz yoki barcha edge og‘irligi teng grafda;
Dijkstra — manfiy bo‘lmagan og‘irliklarda;
Bellman–Ford — manfiy edge’larni qo‘llay oladi va reachable negative cycle’ni aniqlashi mumkin;
Floyd–Warshall — barcha vertex juftlari orasidagi shortest path uchun, odatda O(V³).

Algoritmni “graf weighted ekan” degan yagona belgiga qarab tanlab bo‘lmaydi. Og‘irlik manfiymi, bitta startmi yoki barcha juftlarmi, graf hajmi va zichligi qanday — bular muhim.

Topological sort

DAG vertexlarini har u → v edge uchun u vdan oldin keladigan tartibda joylaydi. Build dependency, kurs prerequisite va vazifa rejasida ishlatiladi.

A → C
B → C
C → D

Mumkin tartib: A, B, C, D

Bir nechta to‘g‘ri tartib bo‘lishi mumkin. Directed cycle mavjud bo‘lsa topological order yo‘q. Kahn algoritmi in-degree va queue, boshqa usul DFS finishing orderdan foydalanadi.

Minimum spanning tree

Connected weighted undirected grafning barcha vertexlarini cycle’siz, minimal umumiy edge og‘irligi bilan bog‘laydigan tree. Kruskal va Prim keng tarqalgan algoritmlar. Bu shortest-path tree bilan bir xil emas: MST umumiy ulanish narxini, shortest path esa ma’lum yo‘llarning masofasini optimallashtiradi.

Strongly connected components

Directed grafni har vertex boshqasiga yetib bora oladigan maksimal guruhlarga ajratadi. Kosaraju va Tarjan kabi algoritmlar ishlatiladi. Dependency tarmog‘i, modullar sikli va web aloqa tuzilmasini tahlil qilishda foydali.

Union-Find

Dynamic undirected bog‘lanishlarda ikki vertex bir componentdami, componentlarni birlashtirish kerakmi degan savollar uchun disjoint set union ishlatiladi. Kruskal va tarmoq ulanish masalalarida uchraydi. U umumiy graph traversal o‘rnini to‘liq bosmaydi; asosan component membershipni samarali boshqaradi.

Real qo‘llanishlar

Ijtimoiy tarmoq

Foydalanuvchi vertex, do‘stlik undirected edge, follow esa directed edge. “Ikki foydalanuvchi orasida nechta tanishlik bor?” savoli unweighted shortest pathga, community topish connected yoki zich guruhlar tahliliga aylanadi.

Real tarmoqda milliardlab edge bo‘lishi mumkin, shu sababli butun graf bitta kompyuter xotirasiga sig‘masligi va taqsimlangan saqlash talab qilinishi mumkin.

Yo‘l va navigatsiya

Chorraha yoki shahar vertex, yo‘l edge. Og‘irlik masofa, vaqt yoki yo‘l haqi bo‘lishi mumkin. Bir tomonlama yo‘l directed edge bilan ifodalanadi. Eng tez va eng qisqa marshrut turli weight funksiyalarini talab qiladi. Trafik o‘zgarishi edge weightni yangilaydi.

Internet va web

Routerlar vertex, fizik yoki mantiqiy ulanishlar edge. Web graphda sahifa vertex, hyperlink directed edge. Crawler qaysi sahifalarni ko‘rganini setda saqlab, graph traversal qiladi; aks holda link cycle’larida qayta-qayta yuradi.

Dependency graph

Paket, modul yoki build target vertex; “A Bga bog‘liq” directed edge. DAG bo‘lsa topological sort bajarilish tartibini beradi. Cycle A → B → C → A bo‘lsa hech biri boshqasidan oldin mustaqil tugay olmaydi.

Tavsiya tizimi

Foydalanuvchilar, mahsulotlar, filmlar va ularning o‘zaro harakatlari bipartite yoki heterogeneous graph ko‘rinishida ifodalanishi mumkin. “Shu mahsulotni olganlar yana nimani oldi?” savoli umumiy qo‘shnilar va graph signaliga tayanishi mumkin. Amaliy recommendation faqat oddiy traversal emas; ranking va machine learning ham qo‘shiladi.

Kompyuter o‘yinlari

Xarita hududlari vertex, yurish mumkin bo‘lgan o‘tishlar edge. NPC pathfinding shortest-path algoritmidan foydalanadi. Gridni graph sifatida qarash mumkin: har yurish mumkin katak vertex, qo‘shni kataklarga harakat edge. Katta o‘yinlarda navmesh yoki iyerarxik graph ishlatilishi mumkin.

Afzalliklari

Ixtiyoriy ko‘pdan-ko‘p munosabatlarni tabiiy ifodalaydi.
Yo‘l, reachability, dependency va network masalalarini umumiy modelga keltiradi.
Directed, weighted va boshqa xususiyatlar real munosabatni aniq aks ettiradi.
Adjacency list sparse ma’lumotni O(V+E) xotirada saqlaydi.
BFS va DFS bilan barcha reachable tuzilmani O(V+E) vaqtda ko‘rish mumkin.

Bu moslashuvchanlik murakkab invariantlar, cycle nazorati va vazifaga mos algoritm hamda representation tanlash zarurati evaziga keladi.

Cheklovlari

Grafni tushunish va debug qilish chiziqli tuzilmalardan murakkabroq.
Adjacency matrix katta sparse grafda O(V²) xotira isrof qiladi.
Adjacency listda edge lookup degree’ga bog‘liq sekin bo‘lishi mumkin.
Cycle traversalni cheksiz aylantirishi mumkin, visited zarur.
Eng qisqa yo‘l turi edge og‘irliklariga qarab boshqa algoritm talab qiladi.
Juda katta graf xotiraga sig‘masligi mumkin.
Vertex va edge’larni parallel o‘zgartirish consistency va synchronization talab qiladi.
Graf diagrammasi katta tarmoqda tezda o‘qib bo‘lmaydigan holga keladi; algoritmik representation zarur.

Keng tarqalgan xatolar va edge case’lar

Directed va undirected edge’ni aralashtirish

Undirected edge adjacency listga ikki tomonda, directed edge faqat o‘z yo‘nalishida yoziladi. Bir tomonni unutish yoki ortiqcha teskari edge qo‘shish reachability natijasini o‘zgartiradi.

Visited ishlatmaslik

Cycle yoki bir vertexga bir nechta path mavjud grafda traversal takrorlanadi, hatto cheksiz yurishi mumkin. Visited vertex ID bo‘yicha boshqariladi; pathlar emas, kerakli holat kuzatiladi.

Disconnected grafni bitta start bilan tugatish

Bitta BFS/DFS faqat start componentini ko‘radi. “Grafdagi barcha vertex” talab qilinsa, tashqi loop barcha unvisited vertexlardan yangi traversal boshlaydi.

BFS har qanday weighted grafda shortest path beradi deb o‘ylash

BFS eng kam edge sonini topadi. Og‘irliklar har xil bo‘lsa, edge soni eng kichik path vazni eng kichik bo‘lmasligi mumkin. Manfiy bo‘lmagan weight uchun Dijkstra kabi algoritm kerak.

Dijkstrani manfiy edge bilan ishlatish

Dijkstra eng yaqin vertexni final deb belgilash g‘oyasiga tayanadi. Manfiy edge keyinroq allaqachon final qilingan masofani yaxshilashi mumkin. Kirish shartlari tekshiriladi.

Tree qoidalarini umumiy grafga qo‘llash

Graf vertexining bir nechta parentga o‘xshash kiruvchi yo‘li, cycle va disconnected componenti bo‘lishi mumkin. Rekursiv tree traversalni visitedsiz umumiy grafga ko‘chirish xavfli.

Adjacency matrixdagi “edge yo‘q” qiymati

0 weight haqiqiy edge bo‘lishi mumkin. 0ni “edge yo‘q” deb ishlatish zero-weight edge’ni ifodalay olmaydi. Alohida boolean, infinity yoki maxsus sentinel kerak. Sentinel haqiqiy weight bilan adashmasligi shart.

Parallel edge va self-loopni unutish

Algoritm simple grafni kutadimi yoki multigraphni qo‘llaydimi aniqlanadi. Parallel edge degree, shortest path va edge soniga ta’sir qiladi. Self-loop directed cycle va degree hisobiga ta’sir qilishi mumkin.

Vertex ID va array indexini aralashtirish

user_5000 kabi ID arrayning 5000-indexida turishi shart emas. Siqilgan ichki index mapping yoki hash map kerak bo‘lishi mumkin. Tashqi IDni to‘g‘ridan-to‘g‘ri ulkan array indexiga aylantirish xotira isrof qiladi.

Adjacency listda duplicate edge

ADD_EDGE(A, B) bir necha marta chaqirilsa, neighbor listda duplicate paydo bo‘lishi mumkin. Bu traversalning ortiqcha ishiga va degree hisobining buzilishiga olib keladi. Model parallel edge’ga ruxsat bermasa, set yoki mavjudlik tekshiruvi ishlatiladi.

Traversal tartibiga ortiqcha tayanish

BFS yoki DFSning aniq tartibi neighbors saqlanish tartibiga bog‘liq. Algoritm correctness faqat “A, B, C” aniq tartibga tayanmasligi kerak, agar qo‘shnilar ataylab saralanmagan bo‘lsa.

Rekursiv DFS chuqurligi

Uzun zanjir shaklidagi grafda recursion depth O(V) bo‘ladi va call stack to‘lishi mumkin. Tashqi yoki juda katta grafda explicit stackli iterativ DFS xavfsizroq.

Mutable vertexni map kaliti qilish

Vertex hash/equalityga ta’sir qiluvchi holati o‘zgarsa, adjacency mapda topilmay qolishi mumkin. Barqaror immutable IDni kalit, o‘zgaruvchi ma’lumotni alohida qiymat sifatida saqlash ma’qul.

Qachon graf ishlatish kerak?

Graf quyidagi ma’lumot tabiatiga mos:

obyektlar orasida ko‘pdan-ko‘p aloqalar mavjud;
yo‘nalish va reachability muhim;
marshrut, dependency yoki network ifodalanadi;
bir obyektga bir nechta turli yo‘l orqali yetish mumkin;
shortest path, component, cycle yoki ordering topish kerak;
tree’dan ko‘ra erkinroq bog‘lanish mavjud.

Avval vertex va edge nimani anglatishini, edge directed va weighted ekanini hamda eng ko‘p bajariladigan amalni aniqlash kerak. Shundan keyin representation va algoritm tanlanadi.

Qachon graf ishlatmaslik kerak?

Quyidagi vaziyatlarda sodda tuzilma yaxshiroq:

Ma’lumot oddiy ketma-ketlik bo‘lsa, array yoki linked list aniqroq.
Qat’iy parent-child iyerarxiya va yagona parent bo‘lsa, tree modeli sodda.
Faqat kalit bo‘yicha lookup kerak bo‘lsa, hash table grafdan kamroq murakkab.
Kichik fixed gridda faqat koordinata bo‘yicha kirish kerak bo‘lsa, 2D array yetarli; uni graphga aylantirish ortiqcha xotira bo‘lishi mumkin.
Faqat navbat tartibi kerak bo‘lsa, queue; LIFO kerak bo‘lsa stack mos.
Munosabatlar yo‘q yoki algoritm ulardan foydalanmasa, edge tuzilmasi ortiqcha.

Grid pathfindingda graph modeli algoritmik fikrlash uchun foydali bo‘lsa ham, barcha edge’larni alohida saqlash shart emas: qo‘shnilar koordinatalardan kerak paytda hisoblanishi mumkin. Bu implicit graph deyiladi va xotirani tejaydi.

Eng muhim xulosa

Graf vertexlar va ular orasidagi edge’lardan iborat. Vertex obyektni, edge munosabatni bildiradi. Edge directed yoki undirected, weighted yoki unweighted bo‘lishi mumkin; graf cycle’li, cycle’siz, connected yoki disconnected bo‘ladi. Bu xususiyatlar qaysi algoritm to‘g‘ri ekanini belgilaydi.

Graf diagramma shaklida tushuntirilsa-da, xotirada edge list, adjacency list yoki adjacency matrix orqali saqlanadi. Adjacency list sparse grafda O(V+E) xotira va samarali neighbor traversal beradi. Adjacency matrix O(V²) xotira evaziga edge lookupni O(1) qiladi.

BFS queue bilan qatlamma-qatlam yuradi va unweighted grafda eng kam qirrali pathni topadi. DFS stack yoki rekursiya bilan chuqurlashib, cycle, component va dependency tahliliga asos bo‘ladi. Ikkalasi adjacency listda O(V+E) vaqt oladi. Cycle va ko‘p yo‘lli bog‘lanish sabab visited nazorati muhim.

Graf tanlashdan oldin beshta savol bering:

Vertex va edge real tizimda nimani anglatadi?
Edge yo‘naltirilganmi?
Og‘irlik bormi va u nimani o‘lchaydi?
Graf sparse yoki dense’mi?
Asosiy talab edge lookup, neighbor traversal, shortest path yoki tartibmi?

Grafning fundamental modelini tushungach, keyingi bosqichda BFS, DFS, topological sort, shortest path, minimum spanning tree va strongly connected component algoritmlarini alohida chuqur o‘rganish mumkin. Har bir algoritm “graf uchun ishlaydi” degan umumiy jumladan ko‘ra aniqroq kirish shartlari va kafolatlarga ega.