Graph'dagi aylanalarni topiş
Graph'da aylana (cycle) nimaligi haqida graph atamalarida tuşuntirilgan. Bir graph'da aylanalar bir neça bölişi mumkin.
Algoritmlar
Graph masalalari. Bipartite graph
Agar graph'ning har bir vertex'i qarama-qarşi tomondagi vertex'ga boğlanuvçi ikki subset'ga (qismga) ajraladigan bölsa, demak graph - bipartite böladi.
Graph'da boğlangan komponentlar
Boğlangan komponentlar (Connected components, CC) deb graphdagi bir-biriga toğridan töğri yoki oradagi vertex'lar orqali boğlangan komponentlar töplamiga aytiladi. Amaliyotda agar ikki vertex orasida path bölsa, biz ularni boğlangan deb ayta olamiz.
Breadth first search algoritmi
Breadth first search (BFS) algoritmi graph'ning barça vertex'larini körib çiqişning yana bir yöli bölib, u rekursiv algoritm hisoblanmaydi. BFS Depth first search algoritmidan farqli ravişda queue işlatadi (DFS - stack'dan foydalanardi).
Depth first search algoritmi
Depth first search (DFS) algoritmi oson klassik graph algoritmlaridan biri bölib, u rekursiya içida graph'dagi barça vertex'larni tekşirib çiqişga yordam beradi. Aslida biz bu algoritmdan binary search tree'dagi barça ma'lumotlarni körib çiqiş uçun foydalanib, traverse() funksiyasini yozganmiz.
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.
Graph ma'lumotlar tuzilmasi
Biz çiziqli bölmagan ma’lumotlar tuzilmasini örganişni boşlaganimizda, ularning bazaviy xarakteristikasini körib çiqqandik: tuzilmadagi ma’lumotlar qandaydir tartibga ega emas (heç bölmaganda sanoq tartibiga ega emas).
Hash table'da collision'ni bartaraf qiliş. Separate chaining va Linear probing
Agar biz özimiz hash funksiya yozadigan bölsak, albatta collision'da nima qiliş kerakligini ham aniqlab olişimiz kerak. Collision'ning yeçimi sifatida ikki usul keltirilgan: Separate chaining va Linear probing.
Hash table va Javascriptda hash table'ni ifodalaş
Hash table (hashtable, hash, hash map) - key'larni value juftlarini boğlaydigan ma'lumot tuzilmasi. Kodda köpinça assotsiativ array (Javascriptda object) körinişida ifodalanadi. Hash table'ning dictionary'dan farqi - array indekslari integer bölib, hash funksiya yordamida generatsiya qilinadi va ind
2D rectangle intersection search
2D rectangle intersection search deb, berilgan N ta töğri törtburçaklar orasidan ustma-ust tuşganlarini topişga aytiladi.