Graph’dagi aylanalarni topish
Graph’da aylana (cycle) nimaligi haqida graph atamalarida tushuntirilgan. Bir graph’da aylanalar bir necha bo’lishi mumkin.
Graph masalalari. Bipartite graph
Agar graph’ning har bir vertex’i qarama-qarshi tomondagi vertex’ga bog’lanuvchi ikki subset’ga (qismga) ajraladigan bo’lsa, demak graph – bipartite bo’ladi.
Graph’da bog’langan komponentlar
Bog’langan komponentlar (Connected components, CC) deb graphdagi bir-biriga tog’ridan to’g’ri yoki oradagi vertex’lar orqali bog’langan komponentlar to’plamiga aytiladi. Amaliyotda agar ikki vertex orasida path bo’lsa, biz ularni bog’langan deb ayta olamiz.
Breadth first search algoritmi
Breadth first search (BFS) algoritmi graph’ning barcha vertex’larini ko’rib chiqishning yana bir yo’li bo’lib, u rekursiv algoritm hisoblanmaydi. BFS Depth first search algoritmidan farqli ravishda queue ishlatadi (DFS – stack’dan foydalanardi).
Depth first search algoritmi
Depth first search (DFS) algoritmi oson klassik graph algoritmlaridan biri bo’lib, u rekursiya ichida graph’dagi barcha vertex’larni tekshirib chiqishga yordam beradi. Aslida biz bu algoritmdan binary search tree’dagi barcha ma’lumotlarni ko’rib chiqish uchun foydalanib, traverse() funksiyasini yozganmiz.
Graph’ni kodda ifodalash. Graph API
Graph ma’lumotlar tuzilmasini kodda ifodalashning bir necha usullari bor. Amaliyotda qo’yiladigan masalaga qarab usullardan biri tanlanadi.
Graph ma’lumotlar tuzilmasi
Biz chiziqli bo’lmagan ma’lumotlar tuzilmasini o’rganishni boshlaganimizda, ularning bazaviy xarakteristikasini ko’rib chiqqandik: tuzilmadagi ma’lumotlar qandaydir tartibga ega emas (hech bo’lmaganda sanoq tartibiga ega emas).
Hash table’da collision’ni bartaraf qilish. Separate chaining va Linear probing
Agar biz o’zimiz hash funksiya yozadigan bo’lsak, albatta collision’da nima qilish kerakligini ham aniqlab olishimiz kerak. Collision’ning yechimi sifatida ikki usul keltirilgan: Separate chaining va Linear probing.
Hash table va Javascriptda hash table’ni ifodalash
Hash table (hashtable, hash, hash map) – key’larni value juftlarini bog’laydigan ma’lumot tuzilmasi. Kodda ko’pincha assotsiativ array (Javascriptda object) ko’rinishida ifodalanadi. Hash table’ning dictionary’dan farqi – array indekslari integer bo’lib, hash funksiya yordamida generatsiya qilinadi va indekslar unikal bo’ladi.
2D rectangle intersection search
2D rectangle intersection search deb, berilgan N ta to’g’ri to’rtburchaklar orasidan ustma-ust tushganlarini topishga aytiladi.