Depth-First Search
ডেপথ-ফার্স্ট সার্চ
এক branch পুরো গভীরে গিয়ে তারপর পিছিয়ে আসা traversal — recursion বা explicit stack-এ চলে, O(V+E); cycle detection থেকে SCC পর্যন্ত সবকিছুর ভিত।
also: dfs, depth first search
প্রতিটা node-এ দুটো timestamp রাখো: discovery time (ঢুকেছে) আর finish time (সব child শেষ করেছে)। Edge গুলো তখন শ্রেণি পায়:
| Edge type | চেনা যায় | মানে |
|---|---|---|
| Tree | নতুন node আবিষ্কার | DFS forest-এর ধার |
| Back | পূর্বপুরুষে ফেরা | cycle আছে |
| Forward/Cross | আগে শেষ হওয়া subtree-তে | DAG structure |
Back edge মানেই directed cycle। Topological sort (finish order উল্টে দিলেই), strongly connected components (Kosaraju/Tarjan), bridge ও articulation point — সব DFS-এর timestamp-এই দাঁড়ায়।