Graphs — Visual Explanation¶

দুই personality, এক map। BFS ছড়ায় পুকুরে ঢেউয়ের মতো। DFS ডুব দেয় সুতোর বল হাতে এক explorer-এর মতো।

এই file টা ছোট ছোট উদাহরণে দুটো fundamental traversal-কে animate করে। প্রতিটা frame পেন্সিল দিয়ে trace করো, আর পরের frame পড়ার আগে নিজে predict করো।

Part 1 — BFS: level by level ছড়িয়ে পড়া ঢেউ¶

BFS explore করে distance order-এ: আগে 1 step দূরের সবকিছু, তারপর 2 step দূরের সবকিছু, এভাবে — পানিতে পাথর ফেললে যেমন ঢেউ ছড়ায়। এই order টা যে machine enforce করে, সেটা একটা queue (first in, first out)।

আমরা একটা ছোট grid maze-এ BFS চালাব। S হলো start, # হলো wall, চলাচল up/down/left/right। Number গুলো দেখায় কোন BFS step-এ প্রতিটা cell আবিষ্কৃত হলো — যেটা ঠিক S থেকে তার shortest distance।

The maze:                Legend:  S start   # wall   . open
    S . . #
    # # . .
    . . . #

Frame 0 — পাথরটা ফেলো¶

    0 . . #          queue: [(0,0)]
    # # . .          discovered so far: S at distance 0
    . . . #

Frame 1 — distance-1 ring¶

S pop করো। তার একমাত্র open neighbor হলো ডানের cell-টা (নিচে wall)।

    0 1 . #          queue: [(0,1)]
    # # . .          the "wave" is the set of 1-cells
    . . . #

Frame 2 — distance-2 ring¶

1-cell টা pop করো। Open neighbors: ডানে।

    0 1 2 #          queue: [(0,2)]
    # # . .
    . . . #

Frame 3 — ঢেউ wall-এর পাশ দিয়ে বেঁকে যায়¶

2-cell টা pop করো। Open neighbors: নিচে (তার ঠিক নিচের cell-টা)।

    0 1 2 #          queue: [(1,2)]
    # # 3 .
    . . . #

Frames 4-6 — ঢেউটা ছড়াতেই থাকে, প্রতি distance-এ একটা ring¶

    0 1 2 #          0 1 2 #          0 1 2 #
    # # 3 4          # # 3 4          # # 3 4
    . . 4 #          . 5 4 #          6 5 4 #
                                          ^
                                 bottom-left reached at distance 6

Key observations:

একই number-ওয়ালা cell গুলো মিলে একটা wave front — queue যেকোনো মুহূর্তে (বড়জোর) দুটো পাশাপাশি front ধরে রাখে।
BFS কোনো cell-কে প্রথমবার ছোঁয়ার সময় যে number টা বসায়, সেটা final — এর চেয়ে ছোট কোনো পথ নেই, কারণ সব ছোট distance আগেই পুরোপুরি explore হয়ে গেছে। এটাই bfs.md-এর হৃৎপিণ্ড।
ঢেউটা পানির মতো wall-এর চারপাশ দিয়ে বয়ে গেল। BFS কোনো কিছুর দিকে "তাক" করে না; সে সবদিকে সমানভাবে flood করে।

Part 2 — DFS: stack নিয়ে গভীরে ডুব¶

DFS একটা neighbor বেছে নিয়ে commit করে — backtrack করার আগে যতটা সম্ভব গভীরে যায়। Machine টা একটা stack — হয় explicit, নয়তো recursion ব্যবহার করলে function-call stack।

একই idea, এবার একটা ছোট graph-এ:

Adjacency (neighbors alphabetically সাজানো): A:[B,C] B:[A,D] C:[A,E] D:[B,F] E:[C,F] F:[D,E]।

আমরা A থেকে recursive DFS চালাই, সবসময় alphabetical order-এ neighbors try করে। Stack column-টা দেখো — এটাই explorer-এর খুলে যাওয়া সুতোর দাগ।

Step | Action                       | Call stack (bottom->top) | Visited
-----+------------------------------+--------------------------+------------------
  1  | visit A, recurse into B      | A                        | {A}
  2  | visit B, recurse into D      | A B                      | {A,B}
  3  | visit D, recurse into F      | A B D                    | {A,B,D}
  4  | visit F, recurse into E      | A B D F                  | {A,B,D,F}
  5  | visit E; nbrs C? not yet ->  | A B D F E                | {A,B,D,F,E}
  6  | visit C; all nbrs seen       | A B D F E C              | {A,B,D,F,E,C}
  7  | C done -> return to E        | A B D F E                |
  8  | E done -> return to F        | A B D F                  |
  9  | F done -> return to D        | A B D                    |
 10  | D done -> return to B        | A B                      |
 11  | B done -> return to A        | A                        |
 12  | A tries C -> already visited | A                        |
 13  | A done. Traversal complete.  | (empty)                  |

Route হিসেবে আঁকলে, dive-টা দেখায় একটা লম্বা ঝাঁপ আর তারপর পিছু হটা:

    A -> B -> D -> F -> E -> C        (the dive)
    C -> E -> F -> D -> B -> A        (the backtrack, unwinding the string)

একই graph-এ A থেকে BFS-এর সাথে তুলনা করো, যেটা ring-এ ring-এ visit করত: A | B C | D E | F। একই nodes, পুরোপুরি আলাদা order — আর order-টাই হলো প্রতিটা algorithm-এর বিক্রির জিনিস:

BFS-এর order বহন করে distance → shortest paths।
DFS-এর order বহন করে structure → components, cycles, finish times, topological order।

Part 3 — `visited` set কেন non-negotiable¶

উপরের graph-এ যেকোনো traversal থেকে visited সরিয়ে নাও, আর step 4 দেখো: F-এর neighbor list-এ D আছে — যে কিনা stack-এ F-এর নিচেই বসে। Set ছাড়া DFS আবার D-তে ঢোকে, তারপর F, তারপর D... চিরকাল। Set ছাড়া BFS nodes-কে exponentially re-queue করে।

Without visited:   A -> B -> D -> F -> D -> F -> D -> ...   (trapped in the cycle)
With visited:      each node entered once; cycle edges quietly skipped

সূক্ষ্ম BFS bug ঠেকানোর নিয়ম: node-কে visited mark করো queue-তে ঢোকানোর মুহূর্তেই, pop করার সময় না। Pop-এ mark করলে, queue-তে বসে থাকা একটা node-কে অন্য কোনো neighbor আবার queue করতে পারে — ভুল count, ফোলা queue, আর weighted-ঘেঁষা problem-এ ভুল distances।

Try it yourself (নিজে করে দেখো)¶

Maze-এর BFS-টা আবার চালাও, কিন্তু (1,3)-এর wall টা সরিয়ে। কোন cell গুলোর number বদলায়?
S থেকে maze-এ DFS চালাও (neighbors-এর order: up, down, left, right)। Cell গুলোতে visit order 0,1,2,... লেখো। BFS-এর stamping থেকে কতটা আলাদা?
A–F graph-এ DFS চালাও, কিন্তু neighbors try করো উল্টো alphabetical order-এ। নিশ্চিত করো visit order বদলায় কিন্তু শেষে visited set টা identical থাকে।
A–F graph-এর cycle টা খুঁজে বের করো (B-D-F-E-C-A-B)। Trace করো ঠিক কোন একটা DFS step এটা টের পায়: যে মুহূর্তে কোনো neighbor already visited আর সে সেই node না, যেখান থেকে আমরা এলাম।

Interactive versions: VisuAlgo-র graph traversal module; reference write-up cp-algorithms BFS আর cp-algorithms DFS-এ।