Dasturchi, frilanser, gik va introvert
Biz o’tgan graph masalalarida asosan undirected graph’larni ko’rib chiqdik. Aslida undirected graph directed graph’dan kodda ifodalanganda bor yo’g’i graph’dagi barcha vertex’larning ikki tomonlama (ikki yo’nalishli) bog’langani bilan farq qiladi. Shuning uchun undirected graph masalalaridagi yechimlar yoki algoritmlar direct graph uchun ham mos kelishi mumkin.
Graph’da aylana (cycle) nimaligi haqida graph atamalarida tushuntirilgan. Bir graph’da aylanalar bir necha bo’lishi mumkin.
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.
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.
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.