Graph — obyektlarni vertex yoki tugunlar, ular orasidagi munosabatlarni edge yoki qirralar orqali ifodalovchi matematik va dasturiy tuzilmadir. Tarmoq qurilmalari, yo‘llar, ijtimoiy aloqalar, dependency, web havolalar va state transition graph modeli bilan tasvirlanadi. Atama ma’lumotlarning chiziqli bo‘lmagan bog‘lanishini umumlashtiradi.
Turlari
Undirected graphda qirra ikki tugun orasidagi o‘zaro bog‘lanish, directed graphda esa u dan v ga yo‘nalishga ega. Weighted graph qirraga masofa, narx yoki sig‘im qiymati beradi. Multigraph bir juft tugun orasida bir nechta qirraga ruxsat beradi.
Self-loop tugunni o‘ziga bog‘laydi. Simple graph odatda self-loop va parallel qirrasiz bo‘ladi. DAG — directed acyclic graph — yo‘naltirilgan cycle’ga ega emas; dependency va task orderingda keng ishlatiladi.
Saqlash usullari
Adjacency list har tugun uchun qo‘shnilar ro‘yxatini saqlaydi. Sparse graph uchun xotira O(V+E) atrofida va qo‘shnilarni ko‘rish samarali. Hash set qirra mavjudligini tez tekshiradi, lekin overhead qo‘shadi.
Adjacency matrix V × V jadval bo‘lib, qirra mavjudligini O(1)da beradi, ammo O(V²) space talab qiladi. Dense graph yoki kichik fixed vertex to‘plamida mos. Edge list faqat qirralarni saqlab, sorting va Kruskal kabi algoritmga qulay.
Traversal
Breadth-first search queue bilan qatlamma-qatlam yuradi va unweighted graphda eng kam qirralik yo‘lni topadi. Depth-first search stack yoki recursion bilan chuqurlashadi; cycle detection, connected component va topological sort uchun asos bo‘ladi.
Visited state bo‘lmasa cycle mavjud graphda traversal cheksiz qaytishi mumkin. Directed cycle tekshiruvida “ko‘rilgan” bilan “joriy recursion stackida” holatlari farqlanadi. Katta graphda recursion stack overflowi sabab iterative variant tanlanishi mumkin.
Yo‘l algoritmlari
Dijkstra non-negative weightli graphda shortest path topadi. Manfiy qirra mavjud bo‘lsa Bellman–Ford mos, negative cycle bo‘lsa finite shortest path bo‘lmasligi mumkin. A* heuristic bilan maqsad tomon qidiruvni yo‘naltiradi.
Minimum spanning tree barcha vertexlarni minimal umumiy og‘irlik bilan bog‘laydi; Kruskal va Prim keng algoritmlardir. Max-flow networkdagi source’dan sinkka maksimal oqimni capacity cheklovi bilan topadi.
Xususiyatlar
Degree tugunga ulangan qirralar soni; directed graphda in-degree va out-degree ajratiladi. Connected component undirected graphdagi o‘zaro reachable tugunlar guruhidir. Strongly connected component directed graphda har ikki yo‘nalishda yetib borish mumkin bo‘lgan maksimal to‘plamdir.
Tree connected va cycle’siz undirected graph. Har V vertexli tree’da V-1 qirra mavjud. Forest bir nechta tree komponentidan iborat. Topological order DAG qirralar yo‘nalishiga mos ketma-ketlik beradi.
Amaliy masalalar
Graph hajmi xotiraga sig‘masa partition, external-memory yoki distributed processing talab qilinadi. Vertex ID mapping, duplicate edge va inconsistent direction data importda tozalanadi. Algoritm complexity’si V va E bilan alohida yoziladi, chunki density natijaga katta ta’sir qiladi.
Graph ma’lumot sifati
Real tizimda vertex va edge vaqt bo‘yicha o‘zgaradi. Snapshot ustida ishlaydigan algoritm update’lar bilan consistent ko‘rinishni qanday olishi kerakligi belgilanadi. Parallel edge va self-loop ayrim hisobni o‘zgartiradi; import ularni ataylab saqlaydimi yoki deduplicate qiladimi hujjatlashtiriladi. Undirected edge faylda ikki yo‘nalish sifatida saqlansa degree hisobida ikki marta sanash xatosi yuz berishi mumkin. Sensitive social graphda hatto tugun nomlari yashirilsa ham topology identity haqida ma’lumot chiqarishi mumkin, shuning uchun access va anonymization talab qilinadi.
Bog‘liq tushunchalar
Vertex, Edge, Breadth-first search, Depth-first search, DAG, Shortest path