Graph’da bog’langan komponentlar

Connected components

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 ma’lumotlar tuzilmasi

Graph

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 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.

Ratchaburi viloyatiga safar

Shanba kuni Ratchaburi viloyatini aylanib keldik. Ratchaburi Bangkokdan 1.5 soatlik yo’l, turistik joyi ko’p emas. Bir-ikki kunlik sayohat uchun yetarli, «для галочки». Dastlab, «Khao Ngu Stone Park»ga kirdik. Park – oddiy park, qoyalar orasida ko’l bor. Tabiiy hududga kichik o’zgarishlar kiritilgan – ko’prik va ko’l ustidan yo’l qurilgan.