Graph'ni kodda ifodalaş. Graph API

Graph ma'lumotlar tuzilmasini kodda ifodalaşning bir neça usullari bor. Amaliyotda qöyiladigan masalaga qarab usullardan biri tanlanadi.

Edge list

Edge list (yoki array) - E miqdordagi edge'larning oddiy ifodalanişi hisoblanadi. Bunda edge'lar array'da vertex juftlari bilan yoziladi. Misol uçun quyidagi graph'ni edge list'da ifodalaş kerak bölsin.

Undirected graph

Biz har bir edge uçun vertex juftlarini array'ga kiritamiz:

[ [1, 2], [2, 3], [3, 1] ]

Oson, töğrimi? Ha, ammo osonlikning tölovi bor.

Edge list'dagi qiymatlar tartiblanmagan. Biz bitta vertex'ning edge'larini topişimiz uçun barça edge'larni tekşirib çiqişimiz kerak. Şunda edge list uçun time complexity - O(E) ga teng böladi. Kiçik graph'larda işlaş tezligi katta farq qilmaydi albatta. Lekin amaliyotda million, milliard edge'lari bölgan graph'larga duç kelamiz. Bunday holatda edge list bizga samaradorlikni taqdim eta olmaydi.

Edge list'ni directed va undirected graph'lar uçun birday işlatiş mumkin.

Undirected graph'larda edge'ni topiş uçun barça edge'larning ikki qiymatini (vertex'ini) tekşiriş kerak bölsa, directed graph'larda bitta tekşiriş yetarli böladi.

Directed graph

[ [1, 2], [2, 3], [3, 1], [3, 4] ]

3 ning edge'larini topiş uçun edge'ning birinçi qiymati 3 ga teng bölgan barça edge'larni olamiz: [3, 1] va [3, 4] . Agar berilgan edge'lar avvaldan tartiblanmagan bölsa, demak işlaş vaqti özgarmasdan qoladi. Birinçi vertex'lari qiymati böyiça tartiblangan directed graph'ning edge list'i uçun esa binary search'ni qöllab köriş mumkin.

Adjacency matrix

Adjacency matrix - graph'dagi qaysi vertex'larda boğlanişlar (edge'lar) borligini ifodalovçi matritsa. Matritsaning eni va böyida vertex'lar, matritsa yaçeykalarida esa ularning boğlanişlari saqlanadi. Agar boğlaniş bölsa, 1 aks holda 0 ifodalanadi. Biz yuqorida körib ötganimiz (1, 2,3) vertex'dan iborat undirected graph'ni Adjacency matrix'da ifodalasak:

| 1 | 2 | 3 |

1 | 0 | 1 | 1 |

2 | 1 | 0 | 1 |

3 | 1 | 1 | 0 |

Adjacency matrix'ning ba'zi foydali hususiyatlari bor:

Agar matritsada içki boğlaniş (self edge) bölmasa, u holda matritsaning diagonali 0 lardan iborat böladi.
Undirected graph uçun matritsaning diagonali simmetrik böladi, ya'ni diagonalning pasti va yuqori qismi bir biriga teng.
Matritsaga qarab graph'ni directed yoki undirected ekanligini aytib beriş mumkin.
Matritsaga edge qöşiş yoki edge öçiriş O(1) vaqt oladi, çunki biz edge qöşiş uçun ikki vertex'ning qiymatini bilganimiz sababli, matritsadan vertex'larni qidirib ötirişimiz şart bölmaydi.

Endi directed graph'ni adjacency matrix'da ifodalasak

| 1 | 2 | 3 | 4 |

1 | 0 | 1 | 0 | 0 |

2 | 0 | 0 | 1 | 0 |

3 | 1 | 0 | 0 | 1 |

4 | 0 | 0 | 0 | 0 |

Adjacency list'ning ham tölovi bor.

V sonli vertex'larga ega graph'ni ifodalaş uçun O(V²) miqdorda xotiradan joy kerak. Agar graph'da edge'lar soni vertex'lar sonidan ança köp bölsa, ya'ni graph ziç (dense) bölsa, matritsa usuli yomon emas. Graph'da edge'lar kam bölganda - siyrak (sparse) holatida, 0 lar bilan töldirilgan, ammo joy isrof qiladigan samarasiz matritsaga ega bölamiz.

Adjacency list

Adjacency list - edge list va adjacency matrix'ning gibrid körinişi bölib, u linked list'lardan iborat array'ga ega. Array elementlari soni - V - graph'dagi vertex'lar soniga teng. Har bir elementdagi linked list esa vertex'ning edge'larini, yoki boşqaça aytganda, qöşni vertex'larini ifodalaydi.

Yuqoridagi undirected graph'ni adjacency list'da ifodalasak:

[ 1 → 2 → 3, 2 → 3 → 1, 3 → 1 → 2]

→ = linked list'dagi pointer.

Directed graph uçun:

[ 1 → 2, 2 → 3, 3 → 1 → 4]

Adjacency list'da vertex'ni topiş vaqti, agar vertex array index'ida ifodalangan bölsa - O(1) ga teng. Masalan graph'dan 3 vertex'ni topiş uçun V[(3 - 1)] qilib murojaat qilamiz. Nima uçun 3 - 1? Sababi vertex'lar array'ning nolinçi elementidan boşlanayotgani uçun.

Vertex'ning barça edge'larini topiş vaqti ham O(1) ga teng. Eng yomon holatda esa O(d) ga. Bunda d - vertex'ning degree'si, vertex'ning edge'lari soni.

E'tibor bergan bölsangiz, directed va undirected graph'larni adjacency list'da ifodalaşda har bir vertex'ning edge'lari soni farq qilmoqda. Undirected graph uçun vertex'lar soni 3, edge'lar soni 6 ta. Directed graph uçun vertex'lar soni 3 ta, edge'lar soni 4 ta. Agar vertex'lar sonini bir xil qoldiriş uçun 4-vertex'ni olib taşlasak, edge'lar soni 3 ta qoladi. Bu degani, undirected graph'da ikki vertex özining edge'larini alohida-alohida ifodalayapti. Ya'ni undirected bölgani uçun bitta edge ikki vertex'da ham takrorlanyapti.

Xulosa qiladigan bölsak, undirected graph'ni adjacency list'da ifodalaş directed graph'ga qaraganda 2*E baravar köp joy oladi. E - edge'lar soni.

API

Adjacent list uçun sodda API. Linked list örniga Set işlatilgan. Set haqida bu yerda tuşuntirilgan: /2020/10/06/dictionary-yoki-symbol-table/

API keyingi mavzularga qarab, töldirib boriladi. Özgarişlarni bu yerda kuzatib borişingiz mumkin: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/graphs/adjacency-list-graph.js

Manbalar:
https://medium.com/basecs/from-theory-to-practice-representing-graphs-cfd782c5be38
Graph editor: https://csacademy.com/app/graph_editor/