Graph traversal — BFS-এর স্তর ও DFS-এর পথ

অধ্যায়ের সূচি · সহজ ব্যাখ্যা ও বাস্তব ব্যবহার · অনুশীলন ও সমাধান

BFS কাছের node-গুলো আগে খোঁজে। DFS একটি পথ ধরে যত দূর সম্ভব যায়, তারপর ফিরে আসে। নিচের ছোট উদাহরণে কোন state বদলাচ্ছে এবং কেন বদলাচ্ছে, তা পাশাপাশি দেখো।

BFS — একটি maze-এ দূরত্ব বসানো

শুরু (0,0)। ওপর, নিচ, বাঁ বা ডানে এক ঘর যাওয়ার খরচ 1। # দেয়াল; · এখনো দেখা হয়নি। সংখ্যা মানে শুরু থেকে সবচেয়ে কম কতটি move লাগে। Highlight করা ঘরগুলো সেই ধাপে নতুন আবিষ্কৃত।

BFS-এর সাতটি distance level

1. দূরত্ব 0 — শুরু

   চিহ্নিত ঘর: 0

   ·

   ·

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ·

   ·

   ·

   ·

   ·

   ফাঁকা বা বাদ দেওয়া ঘর: #

   Queue-তে প্রথমে শুধু (0,0)।

2. দূরত্ব 1 — ডানে এক ঘর

   0

   চিহ্নিত ঘর: 1

   ·

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ·

   ·

   ·

   ·

   ·

   ফাঁকা বা বাদ দেওয়া ঘর: #

   শুরুর নিচে দেয়াল; নতুন খোলা ঘর শুধু (0,1)।

3. দূরত্ব 2 — আবার ডানে

   0

   1

   চিহ্নিত ঘর: 2

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ·

   ·

   ·

   ·

   ·

   ফাঁকা বা বাদ দেওয়া ঘর: #

   (0,1) থেকে নতুন ঘর (0,2)।

4. দূরত্ব 3 — নিচে বাঁক

   0

   1

   2

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   চিহ্নিত ঘর: 3

   ·

   ·

   ·

   ·

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ডানে দেয়াল। এবার (1,2)-এ নামি।

5. দূরত্ব 4 — দুই নতুন ঘর

   0

   1

   2

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   3

   চিহ্নিত ঘর: 4

   ·

   ·

   চিহ্নিত ঘর: 4

   ফাঁকা বা বাদ দেওয়া ঘর: #

   (1,2) থেকে ডানে ও নিচে যাওয়া যায়; দুটোর দূরত্বই 4।

6. দূরত্ব 5 — নিচের সারিতে বাঁয়ে

   0

   1

   2

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   3

   4

   ·

   চিহ্নিত ঘর: 5

   4

   ফাঁকা বা বাদ দেওয়া ঘর: #

   (2,2) থেকে নতুন ঘর (2,1)। (1,3) থেকে নতুন ঘর নেই।

7. দূরত্ব 6 — শেষ খোলা ঘর

   0

   1

   2

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   ফাঁকা বা বাদ দেওয়া ঘর: #

   3

   4

   চিহ্নিত ঘর: 6

   5

   4

   ফাঁকা বা বাদ দেওয়া ঘর: #

   (2,0) থেকে আর নতুন ঘর মেলে না। Queue খালি হলে শেষ।

একই দূরত্বের ঘরগুলো মিলে একটি level। এখানে একটি level-এ দুইটি ঘর আছে, তাই distance level আর queue থেকে pop-এর সংখ্যা এক নয়।

পুরো যে level process হলো	পরের level-এর নতুন ঘর	নতুন দূরত্ব
(0,0)	(0,1)	1
(0,1)	(0,2)	2
(0,2)	(1,2)	3
(1,2)	(1,3), (2,2)	4
(1,3), (2,2)	(2,1)	5
(2,1)	(2,0)	6
(2,0)	নেই	শেষ

Queue ছোট distance-এর node আগে process করে। আরও ছোট পথ থাকলে সেই পথের আগের node থেকেই ঘরটি আগে আবিষ্কৃত হতো। তাই সমান edge cost-এর graph-এ প্রথমবার পাওয়া distance-ই shortest distance। BFS-এর পূর্ণ ব্যাখ্যা।

DFS — গভীরে যাওয়া, তারপর ফিরে আসা

এবার ছয়টি node-এর একটি undirected graph। রেখার দুই দিকেই যাওয়া যায়। প্রতিবেশী একাধিক হলে alphabetically ছোট নাম আগে নেব।

flowchart TD
  A((A)) --- B((B))
  A --- C((C))
  B --- D((D))
  C --- E((E))
  D --- F((F))
  E --- F

Node	সাজানো প্রতিবেশী
A	B, C
B	A, D
C	A, E
D	B, F
E	C, F
F	D, E

Recursive DFS-এর call stack-এ বাম দিক bottom, ডান দিক top। প্রথম ছয় ধাপে node আবিষ্কার হয়; পরের ধাপগুলোতে অসমাপ্ত call শেষ করি।

ধাপ	কাজ	কাজের পরে call stack	নতুন visited
1	A visit; B-তে যাব	A	A
2	B visit; A দেখা, D-তে যাব	A B	B
3	D visit; B দেখা, F-এ যাব	A B D	D
4	F visit; D দেখা, E-তে যাব	A B D F	F
5	E visit; C-তে যাব	A B D F E	E
6	C visit; A ও E দুটোই দেখা	A B D F E C	C
7	C শেষ; E-তে ফিরি	A B D F E	—
8	E-এর F-ও দেখা; F-এ ফিরি	A B D F	—
9	F শেষ; D-তে ফিরি	A B D	—
10	D শেষ; B-তে ফিরি	A B	—
11	B শেষ; A-তে ফিরি	A	—
12	A-এর পরের neighbor C আগেই দেখা	A	—
13	A শেষ	খালি	—

একই graph-এ দুই traversal-এর সম্পূর্ণ visit order

1. DFS — একটি পথ ধরে গভীরে

   A

   B

   D

   F

   E

   C

   ফেরার ক্রম C → E → F → D → B → A; ফেরার সময় আবার visit গুনি না।

2. BFS — কাছের node আগে

   A

   B

   C

   D

   E

   F

   দূরত্বের স্তর A; তারপর B ও C; তারপর D ও E; সবশেষে F।

BFS-এর ক্রম shortest distance খুঁজতে কাজে লাগে। DFS-এর যাওয়া-ফেরার ক্রম দিয়ে connected component, cycle ও finish time বোঝা যায়; directed acyclic graph-এ topological order-ও পাওয়া যায়।

visited কখন বসাতে হবে

এই graph-এ visited বাদ দিলে DFS শুরুতেই A → B → A ফিরে আসে। তাই D পর্যন্ত পৌঁছানোর আগেই একই দুই node বারবার চলতে থাকে।

flowchart LR
  start["প্রতিবেশী পাওয়া গেল"] --> seen{"আগে আবিষ্কৃত?"}
  seen -->|হ্যাঁ| skip["এড়িয়ে যাও"]
  seen -->|না| mark["visited চিহ্ন দাও"]
  mark --> next["BFS: queue-তে দাও / DFS: ভেতরে যাও"]

BFS-এ queue-তে ঢোকানোর সময় visited বসাও। Pop করার সময় পর্যন্ত অপেক্ষা করলে একাধিক neighbor একই node আবার queue-তে ঢোকাতে পারে। অপ্রয়োজনীয় কাজ বাড়ে এবং distance/count update-এর যুক্তি ভুল হওয়ার সুযোগ তৈরি হয়।

নিজে চেষ্টা করো

1. Maze-এর (0,3) দেয়াল সরালে কোন distance বদলায়?
2. Maze-এ DFS চালাও; neighbor order ওপর, নিচ, বাঁ, ডান। ঘরগুলোতে visit order লেখো, তারপর BFS distance-এর সঙ্গে তুলনা করো।
3. A–F graph-এ উল্টো alphabetical neighbor order নিলে DFS-এর output কী হয়?
4. Cycle B–D–F–E–C–A–B-তে DFS কোন edge দেখে cycle ধরতে পারবে? Undirected graph-এ যে parent থেকে এসেছ তার edge-কে আলাদা করতে ভুলবে না।

চলমান উদাহরণ: VisuAlgo graph traversal। আরও পড়া: BFS, DFS।