Topological sort

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

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.