Biz çiziqli bölmagan ma'lumotlar tuzilmasini örganişni boşlaganimizda, ularning bazaviy xarakteristikasini körib çiqqan edik: tuzilmadagi ma'lumotlar qandaydir tartibga ega emas (heç bölmaganda sanoq tartibiga ega emas). Masalan tree node'lari tartiblanmagan, node'lar faqat pointer orqali boşqa node'larga boğlanişi mumkin. Tree'lar aniq bir qoidalarga böysunadi. Bitta root node böladi, uning çild'lari bölmasligi yoki birneça çild'larga ulangan bölişi va hokazo. Ba'zi tree'lar öziga xos hususiyatlarga ega - binary search tree da faqat ikki boğlaniş va ularda bittadan node bölişi mumkin xolos.

Ok, tree'dagi node'lar aniq qoidalar böyiça bir biriga boğlanar ekan. Biz boğlaniş qoidalariga amal qilmasakçi? Masalan root tuşunçasi bölmasa, hamma node'lar bir xil darajada bölsa, istalgan node'ni istalgan node'ga boğlaş imkoni bölsa... Buning imkoni bor albatta - graph ma'lumotlar tuzilmasi bilan.

Tree aslida graph'ning ma'lum bir çeklov va qoidalarga asoslangan varianti xolos. Qisqaça aytganda, istalgan tree bu graph, ammo istalgan graph tree emas.

Tree va Graph. Image credit: https://medium.com/swlh/data-structures-graphs-50a8a032db03

Graph bu har bir node boşqa node'larga boğlangan (boğlanişi mumkin bölgan) node'lar kolleksiyasi.

Graph'ning edge'lari (tomonlari) ikki turda bölişi mumkin:

1. Directed edges (yönalişli tomonlar) - node'lar örtasidagi boğlaniş bir tomonlama (unidirectional) böladi. Birinçi node - yönalişning boşlanişi, ikkinçi node - manzil dib qaraladi.
2. Undirected edges (yönalişsiz tomonlar) - node'lar ikki taraflama boğlangan böladi.

Odatda graph'lar edge'larning turiga qarab, directed graph va undirected graph ga ajratiladi. Ba'zan bir graph'da ikki turdagi edge'lar ham qatnaşgan bölişi mumkin.

Graph atamalari

class GraphAtamalar extends TreeAtamalar ;)
Tree mavzusidagi atamalarning aksariyati graph'lar uçun ham qöllaniladi. Qöşimça atamalarni quyida keltirib ötamiz:

Vertex (yoki vertice, köplikda vertices) - node'ning özi. Node köproq amaliyotda qöllaniladi, vertex nazariyada. Şuning uçun ham graph mavzularida vertex yoki vertice deganimizda node'ni tuşunib olaverasiz.

Path - ikki va undan köp node'lar orasidagi yöl. Path uzunligi soni path'dagi node'lar orasidagi edge'lar soniga teng böladi.

Cycle - agar node'lar orasidagi yöl (path) yopiq, aylana körinişida bölsa, ya'ni yöl boşlaniş node'da tugasa, demak path - cycle böladi. Cycle uzunligi soni ham path'dagi kabi node'lar orasidagi edge'lar soniga teng.

Degree (daraja) - node'ning boşqa node'larga boğlanişlari soni. Agar node boşqa 3ta node'ga boğlangan bölsa, uning degree'si 3 ga teng böladi.

Graph atamalari

Graph qaçon işlatiladi?

Real hayotdagi juda köp tizimlar graph'larga asoslangan böladi. Masalan Facebook ijtimoiy tarmoğidagi döstlik aloqalari undirected graph'ga asoslangan. Siz Facebookdagi döstingiz uçun ham döst hisoblanasiz. Ya'ni döstlik ikki tomonlama boğlangan.

Twitter va Instagram tarmoqlaridagi döstlik (yoki kuzatiş - follow) esa bir tomonlama boğlanişga ega. Siz kuzatadigan odamlar sizni kuzatmasligi mumkin. Demak Twitter va Instagramdagi following - directed graph hisoblanadi.

Şuningdek, xaritalarni graphga aylantiriş mumkin. çorrahalarni (köçalarning boğlanişlarni) node deb oladigan bölsak, köçalarning özi edge böladi. Kartani graph'ga aylantirgaç, siz bir nuqtadan boşqasiga eng qisqa yölni hisoblaş imkoniga ega bölasiz.

Boşqa misollar:

Graph'larning işlatilişiga misollar. Image credit: COMP551: Graph Representation Learning

Weighted edges

Köçalar (yoki şaharlar) orasidan eng qisqa yölni tanlaş misoliga töxtaladigan bölsak, xaritani graph'larda ifodalaşning özi qisqa yölni topiş uçun kamlik qiladi. Sababi qisqa yölni topişga yana köçalarning uzunligi, köçadagi traffikning kamligi, köçadagi tezlikning çeklanganligi kabi faktorlar ham muhim rol öynaydi. Faktorlar asosida biz köçalarning afzalliklarini nisbiy sonlar bilan belgilab çiqamiz. Uşbu afzallik ölçovi uçun weighted edges atamasi kiritilgan. Weight soni yuqori bölgan edge afzalroq edge deb baholanadi.

Weighted edges. Image credit: https://medium.com/swlh/data-structures-graphs-50a8a032db03

Yuqoridagi graph asosida A şahardan H şaharga yetib oliş uçun eng qisqa yölni topiş kerak bölsin. Biz A dan H gaça bölgan barça path'larni edge'larning uzunligi böyiça hisoblab köramiz.

1. A → B → C → D → H = 200 + 180 + 100 + 100 = 580
2. A → B → C → G → D → H = 200 + 180 + 100 + 150 + 100 = 730
3. A → E → D → H = 600 + 350 + 100 = 1050
4. A → F→ I → E → D → H = 150 + 250 + 150 + 350 + 100 = 1000

Uçinçi path'ning umumiy soni 1050, demak bu path boşqa path'lardan afzalroq ekan.

Graph traversal

Albatta biz graph'lar içidan qisqa (yoki afzal) path'ni topiş uçun qölda hisoblab ötirmaymiz. Ayniqsa katta graph'lar uçun hisoblaşlar inson uçun köp vaqt talab qiladi. Şuning uçun biz "qora işlarni" kompyuterga, aniqroği algoritmlarga qöyib beramiz.

Qisqa path'ni topiş uçun barça pathlarni tekşirib çiqiş kerakligi sababli, algoritmlar graph'ni öqib çiqadi - traversal.

Graph'lar uçun traversal'ning ikki turi bor:

• Depth first search (DFS)
• Breadth first search (BFS)