Topic 02 · Graph
BFS ও DFS — Graph Traversal
পরীক্ষায় আসার সম্ভাবনা সবচেয়ে বেশি এই টপিকটার। Queue আর Stack এর প্রতিটা ধাপ
টেবিল আকারে দেখাতে হবে — শুধু final order লিখলে অর্ধেক নম্বর কাটা যায়।
Exam Chance ≈ 95%
★★★
সময় ≈ ২০ মিনিট
O(V + E)
১. প্রশ্ন (Question)
EXAM QUESTION
নিচের undirected graph টির জন্য —
(a) A থেকে শুরু করে BFS traversal করো এবং প্রতিটি ধাপে Queue এর অবস্থা দেখাও।
(b) A থেকে শুরু করে DFS traversal করো এবং প্রতিটি ধাপে Stack এর অবস্থা দেখাও।
(c) BFS ব্যবহার করে A থেকে F এর shortest path বের করো।
E = { A–B, A–C, B–D, B–E, C–F, E–F }
প্রতিবেশী alphabetical ক্রমে নিতে হবে।
২. Prerequisite Concepts (আগে যা জানা দরকার)
২.১ Traversal মানে কী?
Traversal মানে graph এর প্রতিটা vertex ঠিক একবার করে ঘুরে দেখা। Array বা linked list
এ শুরু থেকে শেষ পর্যন্ত গেলেই হয়ে যায়, কিন্তু graph এ অনেক দিকে যাওয়ার রাস্তা থাকে — তাই
একটা নিয়ম লাগে। সেই নিয়ম দুইটা: BFS (চওড়ায়) আর DFS (গভীরে)।
কেন দরকার: নিয়ম না থাকলে একই node বারবার ঘোরা হবে, এমনকি cycle থাকলে অসীম লুপে
পড়ে যাবে। এই জন্যই visited চিহ্ন রাখতে হয়।
২.২ Queue কী? (BFS এ লাগবে)
Queue হলো FIFO (First In, First Out) structure — যে আগে ঢুকবে, সে আগে বের হবে।
ঠিক দোকানের লাইনের মতো। ঢোকানোকে বলে enqueue, বের করাকে বলে dequeue।
কেন দরকার: BFS এ আমরা চাই কাছের node গুলো আগে শেষ হোক, তারপর দূরেরগুলো।
Queue স্বাভাবিকভাবেই এই কাজটা করে — level 1 এর সবাই আগে ঢুকেছে, তাই তারাই আগে বের হবে।
২.৩ Stack কী? (DFS এ লাগবে)
Stack হলো LIFO (Last In, First Out) structure — যে শেষে ঢুকবে, সে আগে বের হবে।
থালার স্তূপের মতো। ঢোকানো = push, বের করা = pop।
কেন দরকার: DFS এ আমরা যত দূর পারা যায় গভীরে যেতে চাই। সর্বশেষ যে node এ গেলাম,
তার পাশ থেকেই পরের ধাপ শুরু করতে হবে — এই "শেষেরটা আগে" আচরণ ঠিক stack এর আচরণ।
Recursion আসলে ভেতরে ভেতরে stack-ই ব্যবহার করে।
২.৪ Visited Array — কেন লাগে?
প্রতিটি vertex এর জন্য একটা visited চিহ্ন রাখা হয় (শুরুতে সব false)। একবার ঘোরা হলে
true করে দেওয়া হয়।
কেন দরকার: A–B আর B–A একই edge। visited না রাখলে A থেকে B, তারপর B থেকে আবার A —
এভাবে অনন্তকাল চলতে থাকবে। খুব গুরুত্বপূর্ণ: BFS এ visited চিহ্ন দিতে হয় queue তে
ঢোকানোর সময়, বের করার সময় নয় — নাহলে একই node দুইবার queue তে ঢুকে যাবে।
২.৫ Level কী? (BFS এ)
Source থেকে কোনো node এ পৌঁছাতে সর্বনিম্ন কয়টা edge পার হতে হয় — সেটাই ওই node এর
level বা distance। Source এর level 0, তার সরাসরি প্রতিবেশীদের level 1, তাদের
প্রতিবেশীদের level 2 — এভাবে।
কেন দরকার: BFS ঠিক level অনুযায়ী এগোয় বলেই unweighted graph এ BFS ই shortest
path দেয়। এটা পরীক্ষার একটা প্রিয় প্রশ্ন।
৩. Exam Definition (English)
Breadth First Search (BFS): BFS is a graph traversal algorithm that starts at a source
vertex and explores all of its neighbours at the present depth level before moving on to the
vertices at the next depth level. It uses a queue (FIFO) and runs in O(V + E)
time using an adjacency list. In an unweighted graph, BFS produces the shortest path from the
source to every reachable vertex.
Depth First Search (DFS): DFS is a graph traversal algorithm that starts at a source
vertex and explores as far as possible along each branch before backtracking. It uses a
stack (LIFO), either explicitly or through recursion, and runs in O(V + E)
time using an adjacency list.
৪. Concept Explanation (বাংলায়)
BFS — চওড়ায় ছড়ানো। কল্পনা করো পুকুরে একটা ঢিল ফেললে। ঢেউটা গোল হয়ে চারদিকে
সমান ভাবে ছড়ায় — আগে কাছেরটা ভেজে, তারপর দূরেরটা। BFS ঠিক তাই করে। A থেকে শুরু করে
প্রথমে A এর সব প্রতিবেশী দেখে (level 1), তারপর তাদের সব প্রতিবেশী (level 2)।
কোনো level অসম্পূর্ণ রেখে পরের level এ যায় না।
DFS — গভীরে ডুব। কল্পনা করো গোলকধাঁধায় ঢুকে একটা দেয়াল ধরে ধরে হাঁটছ। যতক্ষণ
সামনে রাস্তা আছে, ততক্ষণ এগোতে থাকবে। একদম আটকে গেলে (আর নতুন রাস্তা নেই) তখনই
পিছিয়ে আসবে (backtrack) আর পাশের রাস্তাটা ধরবে। DFS ঠিক তাই — এক শাখা পুরো শেষ
না করে অন্য শাখায় যায় না।
৫. Algorithm (English)
BFS
BFS(Graph G, source s)
for each vertex v in G
visited[v] = false
visited[s] = true // mark when ENQUEUEING, not when dequeueing
enqueue(Q, s)
while Q is not empty do
u = dequeue(Q)
print u // u is now finally visited
for each neighbour v of u (in order) do
if visited[v] == false then
visited[v] = true
enqueue(Q, v)
end while
DFS — iterative (stack)
DFS(Graph G, source s)
for each vertex v in G
visited[v] = false
push(S, s)
while S is not empty do
u = top(S)
if u is not visited then
visited[u] = true
print u
if u has an unvisited neighbour v (first in order) then
push(S, v)
else
pop(S) // dead end → backtrack
end while
DFS — recursive (ছোট ও সহজ)
DFS(u)
visited[u] = true
print u
for each neighbour v of u (in order) do
if visited[v] == false then
DFS(v) // recursion = implicit stack
৬. ধাপে ধাপে ব্যাখ্যা (বাংলায়)
ধাপ ১ — Adjacency List বানাও
Edge গুলো থেকে প্রতিটি node এর প্রতিবেশী তালিকা alphabetical ক্রমে লিখে নাও।
কেন দরকার: traversal এর উত্তর সম্পূর্ণভাবে প্রতিবেশীর ক্রমের উপর নির্ভর করে।
তালিকা আগে না বানালে মাঝপথে ক্রম গুলিয়ে যাবে।
ধাপ ২ — Source কে visited করে Queue/Stack এ দাও
BFS এ A কে visited করে enqueue করো; DFS এ A কে push করে visit করো।
কেন দরকার: শুরুর বিন্দু ছাড়া traversal শুরুই করা যায় না। প্রশ্নে source না দিলে
সবচেয়ে ছোট নামের vertex ধরে নাও এবং সেটা লিখে দাও।
ধাপ ৩ — একটা করে বের করো, তার প্রতিবেশী ঢোকাও
BFS: dequeue করো → তার সব unvisited প্রতিবেশী visited করে enqueue করো।
DFS: stack এর top দেখো → তার প্রথম unvisited প্রতিবেশীতে যাও (push)।
কেন আলাদা: BFS এ একসাথে সব প্রতিবেশী ঢুকিয়ে দিই (তাই level সম্পূর্ণ হয়),
DFS এ একবারে একটা ধরে গভীরে নামি।
ধাপ ৪ — আটকে গেলে কী করবে
BFS: কিছুই না, শুধু পরেরটা dequeue করো।
DFS: সব প্রতিবেশী visited হয়ে গেলে
pop করো — এটাই backtrack।
কেন দরকার: DFS এ pop না করলে পিছিয়ে এসে অন্য শাখা ধরা যাবে না,
তখন কিছু node বাদ পড়ে যাবে।
ধাপ ৫ — Queue/Stack খালি হলে থামো
তখন Path সারিতে যে ক্রম দাঁড়িয়েছে, সেটাই উত্তর।
কেন দরকার: graph disconnected হলে খালি হওয়ার পরও কিছু node বাকি থাকতে পারে —
তখন বাকি component থেকে আবার শুরু করতে হবে।
৭. ASCII Diagram
Graph
A
/ \
B C
/ \ \
D E ————— F
6 vertex, 6 edge, undirected
Adjacency List
A → B , C
B → A , D , E
C → A , F
D → B
E → B , F
F → C , E
প্রতিবেশী alphabetical ক্রমে
৮. Q1 সমাধান — BFS (source = A)
Step 1 এ কী করলাম: A কে dequeue করলাম, তার প্রতিবেশী B ও C কে visited করে enqueue করলাম।
কেন: BFS এ একটা node বের করলেই তার সব unvisited প্রতিবেশী একসাথে ঢুকিয়ে দিতে হয় —
এতেই level 1 সম্পূর্ণ হয়।
Step 3 এ খেয়াল করো: C বের হয়ে F কে ঢোকাল। কিন্তু Step 5 এ E বের হয়ে F কে
আর ঢোকায়নি — কারণ F আগেই visited হয়ে গেছে। এই জায়গাটাই সবচেয়ে বেশি ভুল হয়।
BFS Traversal Order: A, B, C, D, E, F
Level 0: A · Level 1: B, C · Level 2: D, E, F
৯. Q2 সমাধান — DFS (source = A)
Step 3 এ কী করলাম: B এর প্রতিবেশী তালিকা A, D, E। A আগেই visited, তাই প্রথম
unvisited হলো D — সেখানে গেলাম। কেন: DFS মানেই "যত দূর পারা যায় গভীরে", তাই
প্রথম যে রাস্তা খোলা পাই সেটাই ধরি।
Step 4 এ কী করলাম: D এর একমাত্র প্রতিবেশী B, সেটা visited — অর্থাৎ D একটা dead end।
তাই D কে pop করে B তে ফিরে এলাম। এটাই backtracking, DFS এর সবচেয়ে গুরুত্বপূর্ণ অংশ।
DFS Traversal Order: A, B, D, E, F, C
পথ: A → B → D (dead end, backtrack) → E → F → C
খেয়াল করো: এখানে C একদম শেষে এলো, যদিও C হলো A এর সরাসরি প্রতিবেশী!
কারণ DFS আগে B এর পুরো শাখা শেষ করেছে, আর সেই শাখা ঘুরে F হয়ে C তে পৌঁছেছে।
BFS এ C ছিল ৩ নম্বরে, DFS এ ৬ নম্বরে — এই পার্থক্যটাই দুইটার চরিত্র।
DFS এর Recursive রূপ (একই উত্তর)
DFS(A) → visit A
DFS(B) → visit B
DFS(D) → visit D → কোনো unvisited প্রতিবেশী নেই → return
DFS(E) → visit E
DFS(F) → visit F
DFS(C) → visit C → return
return
return
return
return
Output: A , B , D , E , F , C
১০. Q3 — BFS দিয়ে Shortest Path (A → F)
BFS চালানোর সময় প্রতিটি node এর Level (দূরত্ব) আর Parent (কার মাধ্যমে এলাম)
লিখে রাখলেই shortest path বেরিয়ে আসে।
| Node | Level (দূরত্ব) | Parent | ব্যাখ্যা |
|---|
| A | 0 | — | Source |
| B | 1 | A | A থেকে সরাসরি |
| C | 1 | A | A থেকে সরাসরি |
| D | 2 | B | B এর মাধ্যমে |
| E | 2 | B | B এর মাধ্যমে |
| F | 2 | C | C এর মাধ্যমে (E এর আগে C পৌঁছেছে) |
Path বের করার নিয়ম: গন্তব্য থেকে Parent ধরে ধরে উল্টো হাঁটো, তারপর উল্টে লেখো।
F ← C ← A (Parent ধরে উল্টো)
A → C → F (উল্টে লিখলাম)
Shortest path A → F = A → C → F · দৈর্ঘ্য = 2 edge
Unweighted graph এ BFS ই shortest path দেয় — DFS দেয় না
DFS দিয়ে করলে ভুল হতো: DFS এ A থেকে F এ পৌঁছেছি A → B → E → F পথে, যার দৈর্ঘ্য 3।
এটা shortest নয়। তাই unweighted shortest path = BFS, এই কথাটা মনে রাখতেই হবে।
১১. BFS vs DFS ও সাধারণ ভুল
তুলনা টেবিল (theory প্রশ্নে প্রায়ই আসে)
| বিষয় | BFS | DFS |
|---|
| Data structure | Queue (FIFO) | Stack (LIFO) / recursion |
| যাওয়ার ধরন | Level by level (চওড়ায়) | গভীরে, তারপর backtrack |
| Unweighted shortest path | দেয় ✓ | দেয় না ✗ |
| Space (worst case) | O(V) — পুরো একটা level | O(h) — গভীরতা |
| Time (adjacency list) | O(V + E) | O(V + E) |
| Time (adjacency matrix) | O(V²) | O(V²) |
| Recursion দিয়ে লেখা যায়? | স্বাভাবিকভাবে নয় | হ্যাঁ, খুব সহজে |
| প্রধান ব্যবহার | Shortest path, level order, নিকটতম খোঁজা | Cycle detection, topological sort, connected component |
Common Mistakes
- Visited চিহ্ন দেরিতে দেওয়া — BFS এ enqueue করার সময়ই visited করতে হবে। dequeue এর সময় করলে একই node একাধিকবার queue তে ঢুকে উত্তর ভুল হবে।
- প্রতিবেশীর ক্রম এলোমেলো করা — প্রশ্নে ক্রম না বললে alphabetical ধরো এবং খাতায় লিখে দাও: "Neighbours are taken in alphabetical order."
- Queue / Stack এর অবস্থা না দেখানো — শুধু final order লিখলে বেশিরভাগ নম্বর কাটা যায়। টেবিল বাধ্যতামূলক।
- DFS এ backtrack (pop) না দেখানো — dead end এ পৌঁছে pop করার ধাপটা টেবিলে থাকতেই হবে।
- Visited node আবার push/enqueue করা — প্রতিবার ঢোকানোর আগে visited যাচাই করতে হবে।
- Disconnected graph এ থেমে যাওয়া — queue/stack খালি হওয়ার পরও unvisited node থাকলে সেখান থেকে আবার শুরু করতে হবে।
- DFS কে shortest path বলা — DFS কখনোই shortest path এর নিশ্চয়তা দেয় না।
১২. Viva ও Practice Questions
Viva Questions
Q: BFS এ Queue আর DFS এ Stack ব্যবহার করা হয় কেন?
Q: Visited array কেন লাগে? না থাকলে কী হবে?
Q: BFS কেন unweighted graph এ shortest path দেয়, কিন্তু weighted এ দেয় না?
Q: DFS এ backtracking বলতে কী বোঝায়? কখন হয়?
Q: BFS ও DFS দুইটারই complexity O(V + E) — এই V আর E কোথা থেকে আসে?
Q: Recursive DFS আর iterative DFS — উত্তরে পার্থক্য হয় কি?
Q: একটা graph এ cycle আছে কিনা DFS দিয়ে কীভাবে বুঝবে?
Q: Disconnected graph এ BFS চালালে কী সমস্যা হয় এবং সমাধান কী?
Practice Questions
- Graph:
1–2, 1–3, 2–4, 3–4, 4–5, 5–6। Vertex 1 থেকে BFS ও DFS করো, দুইটার Queue/Stack টেবিল দেখাও।
উত্তর দেখাও
List: 1→2,3 · 2→1,4 · 3→1,4 · 4→2,3,5 · 5→4,6 · 6→5
BFS: 1, 2, 3, 4, 5, 6
DFS: 1, 2, 4, 3 (backtrack), 5, 6 → 1, 2, 4, 3, 5, 6
DFS ব্যাখ্যা: 1→2→4→3 (3 এর প্রতিবেশী 1, 4 দুইটাই visited → pop) → 4 এ ফিরে 5 → 6।
- উপরের graph এ 1 থেকে 6 এর shortest path কত এবং কোন পথে? Level/Parent টেবিল দিয়ে দেখাও।
উত্তর দেখাও
Level: 1=0, 2=1, 3=1, 4=2, 5=3, 6=4। Parent: 2←1, 3←1, 4←2, 5←4, 6←5।
Path = 1 → 2 → 4 → 5 → 6, দৈর্ঘ্য 4 edge।
- Directed graph
A→B, A→C, B→D, C→D, D→E এ A থেকে BFS ও DFS করো। Undirected এর সাথে পার্থক্য কী হলো?
উত্তর দেখাও
BFS: A, B, C, D, E · DFS: A, B, D, E (dead end → backtrack), তারপর C → A, B, D, E, C
পার্থক্য: directed এ উল্টো দিকে ফেরা যায় না, তাই D থেকে C তে যাওয়া যায়নি।
- একটা graph এ 8টা vertex আছে কিন্তু BFS চালিয়ে মাত্র 5টা visited হলো — এর মানে কী? কী করতে হবে?
- DFS এর recursive pseudocode লেখো এবং প্রতিটা লাইন ব্যাখ্যা করো।
- প্রমাণ করো যে BFS এর সময় জটিলতা adjacency list এ O(V + E)।
- একই graph এ প্রতিবেশীর ক্রম উল্টে দিলে (alphabetical এর বদলে reverse alphabetical) BFS ও DFS এর উত্তর কী দাঁড়াবে?
উত্তর দেখাও
মূল graph এ reverse ক্রমে (A→C,B · B→E,D,A · C→F,A · E→F,B · F→E,C):
BFS: A, C, B, F, E, D · DFS: A, C, F, E, B, D
অর্থাৎ ক্রম বদলালে উত্তরও বদলায় — এই জন্যই ক্রমটা লিখে দিতে হয়।
- BFS ও DFS এর মধ্যে কোনটা দিয়ে "দুইটা node connected কিনা" দ্রুত বলা যায়? ব্যাখ্যা করো।