Qraflarda BFS və DFS
Qrafı gəzməyin iki üsulu var və hər ikisi eyni skeletdən ibarətdir: növbəti node-u götür → əvvəl görməmişiksə emal et → qonşularını əlavə et. Yeganə fərq hansı kolleksiyadan götürdüyündür.
BFS (Breadth-First Search) — queue (FIFO) istifadə edir və qrafı təbəqə-təbəqə gəzir: əvvəl başlanğıcdan 1 addımlıqda olanlar, sonra 2 addımlıqda olanlar. Məhz buna görə BFS weight-siz qrafda ən qısa yolu tapır: bir node-a ilk dəfə çatdığın an, oraya minimum sayda addımla çatmısan.
DFS (Depth-First Search) — stack (LIFO) və ya rekursiya istifadə edir və bir istiqamətdə sona qədər gedir, sonra geri qayıdıb (backtrack) başqa budağı yoxlayır. DFS "ən qısa yol" tapmır, amma qrafın strukturu haqqında suallara cavab verməkdə əvəzsizdir.
Hər ikisinin mürəkkəbliyi O(V + E)-dir: hər vertex bir dəfə emal olunur, hər edge bir dəfə (undirected qrafda iki dəfə) nəzərdən keçirilir. Yaddaş O(V).
Visited dəsti məcburidir. Bu, qraf traversal-ında ən çox buraxılan səhvdir və interview-da dərhal görünür.
Tree-də visited lazım deyil, çünki tree-də cycle yoxdur — hər node-a yalnız bir yolla çatırsan. Qrafda isə iki node bir-birinə göstərə bilər və visited olmadan A → B → A → B ... sonsuz döngəsinə düşürsən.
İki incə detal:
- Node-u queue-ya əlavə edərkən visited kimi işarələ, çıxararkən yox. Əks halda eyni node növbəyə bir neçə dəfə düşür və böyük qraflarda bu, yaddaşı partladır
- Rekursiv DFS-də dərinlik
V-ə çata bilər. 10⁵ node-luq zəncirvari qrafda bu, stack overflow deməkdir — belə hallarda DFS-i açıqstackilə iterativ yaz
DFS-in üç klassik tətbiqi:
- Connectivity / connected components — neçə ayrı "ada" var; hər gəzilməmiş node-dan yeni DFS başladırsan
- Cycle detection — directed qrafda hazırda recursion stack-də olan node-a rast gəlsən, cycle var (bu,
visited-dən AYRI dəstdir); undirected qrafda isə gəldiyin parent-i istisna edirsən - Topological sort — DAG-da DFS bitirdiyi node-ları siyahıya yığır, sonda siyahını tərsinə çevirirsən; nəticə asılılıqları pozmayan sıradır (build sırası, migration sırası)
| Meyar | BFS | DFS |
|---|---|---|
| Struktur | Queue (FIFO) | Stack (LIFO) və ya rekursiya |
| Gəzmə qaydası | Təbəqə-təbəqə, başlanğıca yaxından uzağa | Bir budaqda sona qədər, sonra backtrack |
| Ən qısa yol (weight-siz) | Bəli — zəmanətlə | Xeyr — tapdığı yol ən qısa olmaya bilər |
| Tipik yaddaş | Ən geniş təbəqənin ölçüsü — geniş qraflarda böyük ola bilər | Ən dərin yolun uzunluğu — dərin qraflarda böyük ola bilər |
| Ən yaxşı olduğu məsələlər | Minimum addım sayı, ən yaxın hədəf, level-order, çoxmənbəli yayılma | Connectivity, cycle detection, topological sort, backtracking, bütün yolların sayılması |
| Risk | Queue böyüyə bilər | Rekursiyada stack overflow |
Grid məsələləri gizlədilmiş qraf məsələləridir və interview-da ən çox verilən qraf tapşırıqları məhz bunlardır: number of islands, flood fill, rotting oranges, labirintdə ən qısa yol, ən böyük göl sahəsi.
Çevirmə qaydası sadədir: hər xana bir vertex, qonşu xanalar isə edge. Graph sinfi qurmursan — qonşuları ofsetlərlə hesablayırsan:
- 4 istiqamət:
[[0,1],[1,0],[0,-1],[-1,0]] - 8 istiqamət (diaqonallar da): əlavə olaraq
[[1,1],[1,-1],[-1,1],[-1,-1]]
İki qayda: hər addımda sərhədi yoxla (0 <= r < rows && 0 <= c < cols), və visited-i ya ayrıca matris kimi saxla, ya da (icazə verilirsə) xananı yerində dəyişdir.
Hansını seçmək? Sual "neçə ada var / bu sahə nə qədərdir"dirsə → DFS (və ya BFS, fərqi yoxdur). Sual "minimum neçə addım / neçə dəqiqəyə yayılar"dırsa → mütləq BFS. Sonuncuda çox vaxt multi-source BFS lazım olur: bütün başlanğıc nöqtələrini eyni anda növbəyə yığırsan və eyni təbəqələmə işləyir.
Interview məsləhəti: "BFS, yoxsa DFS?" sualına cavab verərkən seçimini bir cümlə ilə əsaslandır — qiymətləndirilən budur, adı demək yox. "Minimum addım sayı soruşulur, ona görə BFS: ilk dəfə çatdığım an cavabdır. DFS də gəzərdi, amma ən qısa yola zəmanət verməzdi." Əlavə bir bonus cümlə: BFS-i seçəndə addım sayını izləmək üçün ya node-la birlikdə məsafəni saxla, ya da hər dəfə bütün təbəqəni (queue.length qədər) birdən emal et — ikinci üsul daha təmiz oxunur.