Topological Sort — সম্পূর্ণ গাইড Beginner থেকে Exam-Ready · ASCII diagram + প্রতিটা সমাধানের সাথে "Exam Script এ ঠিক এভাবে লিখবে" model answer

📑 সূচিপত্র ১. Prerequisite Concepts → ১.৯ Graph Representation (Adjacency List/Matrix) → ২. Exam Definition (English) → ৩. Method 1 — DFS + Stack Algorithm → ৪. Q1 সমাধান — DFS + Stack (Step-by-Step) → ৫. Method 2 — Kahn's Algorithm → ৬. Q2 সমাধান — Kahn's Algorithm (Step-by-Step) → ৬.৫ DFS vs Kahn's — কোনটা কখন ব্যবহার করবে → ৭. Q3 সমাধান — একাধিক Answer কি Valid? → ৮. Q4 সমাধান — Cycle থাকলে কী হবে? → ৯. সাধারণ ভুলগুলো → ৯.৫ Exam এ Full Marks পাওয়ার Answer-Writing কৌশল → ১০. Practice Questions (Exam-format) → Quick Revision Summary →

অংশ ১: Prerequisite Concepts (আগে যা জানা দরকার)

Topological Sort বুঝতে হলে আগে কিছু basic জিনিস পরিষ্কার থাকতে হবে। একটা একটা করে, diagram ও example সহ শুরু থেকে শিখি।

১.১ Graph কী?

Graph হলো এমন একটা structure যেখানে কিছু Node (বা Vertex) থাকে, আর সেই Node গুলোর মধ্যে সংযোগ থাকে যাকে বলে Edge।

Vertex (V): গ্রাফের একেকটা বিন্দু/পয়েন্ট। যেমন A, B, C, D — এগুলো vertex।
Edge (E): দুইটা vertex এর মধ্যে সংযোগ রেখা। যেমন A→C মানে A থেকে C তে একটা edge আছে।

📌 Example (real-life) ধরো তোমার University তে কিছু Course আছে — Math-1, Math-2, Physics, Programming। এখানে প্রতিটা course একেকটা node। আর "Math-1 শেষ না করে Math-2 নেওয়া যাবে না" — এই সম্পর্কটা একটা edge।

     Level 0          Level 1          Level 2          Level 3

       A  ─────────┐
                    ▼
       B  ───────► C ───────────────► E ─────┐
         │                                     ▼
         └───────► D ─────────────────────────► F

Main Example DAG | Edges: A→C, B→C, B→D, C→E, D→F, E→F | (এই graph টাই পুরো ডকুমেন্টে বারবার ব্যবহার হবে)

১.২ Directed Graph কী? (কেন দরকার?)

Graph দুই ধরনের হয়:

Undirected Graph: edge এর কোনো দিক (direction) নেই। A-B মানে A থেকে B, আবার B থেকে A — দুইটাই সমান। যেমন Facebook friendship।
Directed Graph: edge এর একটা নির্দিষ্ট দিক থাকে। A→B মানে শুধু A থেকে B যাওয়া যায়। যেমন Instagram follow।

কেন directed graph দরকার Topological Sort এ? কারণ Topological Sort মূলত "dependency" বা "কোনটার আগে কোনটা হবে" — এই সম্পর্ক বোঝায়। এটা একটা direction-based সম্পর্ক, তাই এখানে directed edge লাগবে।

📌 Example নিচে দেখো — Math-1 → Math-2 → Physics। এর মানে Math-1 শেষ না করে Math-2 নেওয়া যাবে না, আর Math-2 শেষ না করে Physics নেওয়া যাবে না। তীরগুলো একদিকমুখী (one-way), তাই এটা Directed Graph।

  [ Math-1 ]  ────────►  [ Math-2 ]  ────────►  [ Physics ]

Directed Graph Example — Course Prerequisite Chain

১.৩ Cycle কী? (কেন গুরুত্বপূর্ণ?)

Cycle মানে হলো একটা path যেটা কোনো একটা node থেকে শুরু হয়ে ঘুরে আবার সেই একই node এ ফিরে আসে। উদাহরণ: A→B→C→A।

কেন cycle সমস্যা তৈরি করে? চিন্তা করো — "Course A নিতে হলে আগে Course B লাগবে" (B→A), আবার "Course B নিতে হলে আগে Course A লাগবে" (A→B)। তাহলে কোনটা আগে নিবে?? এটা একটা অসম্ভব (impossible) পরিস্থিতি।

📌 Example নিচে X→Y→Z→X একটা cycle তৈরি করেছে। এখানে X এর আগে Z লাগবে, আবার Z এর আগে Y লাগবে, আবার Y এর আগে X লাগবে — এটা কখনোই সমাধান করা সম্ভব না।

            X
          ╱   ▲
        ▼       ╲
       Y  ─────►  Z

      (X→Y, Y→Z, Z→X — ঘুরে আবার X তে ফেরত আসছে)

⚠️ Cycle Example — এটা DAG না, তাই Topological Sort সম্ভব না

১.৪ DAG (Directed Acyclic Graph) কী?

DAG = Directed + Acyclic (cycle-free) Graph

অর্থাৎ, DAG হলো এমন একটা graph যেখানে: (১) সব edge এর একটা নির্দিষ্ট direction আছে, এবং (২) কোনো cycle নেই।

মনে রাখার কৌশল: DAG = "তীর চিহ্ন আছে, কিন্তু ঘুরে ফিরে আসার কোনো রাস্তা নেই।"

⚠️ সবচেয়ে গুরুত্বপূর্ণ নিয়ম Topological Sort শুধুমাত্র DAG-তে সম্ভব। Cycle থাকলে Topological Sort করা যাবে না।

📌 Example আমাদের Main Example Graph (A→C, B→C, B→D, C→E, D→F, E→F) একটা DAG — কোনো cycle নেই। কিন্তু X→Y→Z→X গ্রাফটা DAG না, কারণ সেখানে cycle আছে।

১.৫ DFS (Depth-First Search) কী?

DFS হলো একটা গ্রাফ traverse (ভ্রমণ) করার পদ্ধতি, যেখানে তুমি একটা node থেকে শুরু করে যতদূর সম্ভব গভীরে (depth) যাও, তারপর পিছিয়ে এসে (backtrack) অন্য পথে যাও।

📌 Example (real-life) গোলকধাঁধায় (maze) হাঁটার সময় তুমি একটা রাস্তা ধরে যতদূর যাওয়া যায় যাও, dead-end পেলে ফিরে এসে অন্য রাস্তা try করো। আমাদের Main Example Graph এ DFS চালালে: A→C→E→F পর্যন্ত গভীরে যাবো (F এ dead-end), তারপর backtrack করবো।

১.৬ In-degree কী?

In-degree মানে একটা node এ কয়টা edge ঢুকছে (incoming)। উদাহরণ: A→C এবং B→C থাকলে, C এর in-degree = 2।

কেন দরকার? In-degree 0 মানে সেই node এর উপর কোনো dependency নেই — অর্থাৎ সেটা সবার আগে করা যায়। এটাই Kahn's Algorithm এর মূল ভিত্তি।

   A  ───┐
          ▼
          C     ◄── in-degree(C) = 2   (দুইটা তীর ঢুকছে)
          ▲
   B  ───┘

In-degree Example

১.৭ Stack কী?

Stack হলো একটা data structure যেখানে LIFO (Last In, First Out) নিয়ম মানা হয় — সবচেয়ে শেষে যেটা ঢুকবে, সবচেয়ে আগে সেটাই বের হবে।

📌 Example (real-life) একটার উপর একটা প্লেট রাখলে, সবার উপরের প্লেটটাই আগে নামাতে হয়। DFS+Stack method এ, একটা node "finish" হয়ে stack এ push হলে, সবার শেষে push হওয়া node ই আমরা top থেকে পড়ার সময় সবার প্রথমে পাবো।

১.৮ Queue কী? (Kahn's Algorithm এ লাগবে)

Queue হলো FIFO (First In, First Out) — যেটা আগে ঢুকবে সেটাই আগে বের হবে।

📌 Example (real-life) দোকানে লাইনে দাঁড়ানো — যে আগে দাঁড়িয়েছে সে আগে সার্ভিস পায়। Kahn's Algorithm এ in-degree 0 হওয়া node গুলো Queue তে ঢোকে, আগে ঢোকা node আগে বের হয়ে process হয়।

১.৯ Graph কে Code/খাতায় কীভাবে লিখবে? — Adjacency List (নতুন সংযোজন)

Exam এ অনেক সময় graph টা edge-list আকারে না দিয়ে Adjacency List আকারে দেওয়া হয়। তাই এটা পড়তে জানা জরুরি।

Adjacency List মানে প্রতিটা node এর পাশে তার সব "সন্তান" (যাদের দিকে সে point করছে) লিস্ট আকারে লেখা।

   A → [C]
   B → [C, D]
   C → [E]
   D → [F]
   E → [F]
   F → []

Main Example Graph-এর Adjacency List রূপ (এটা এবং edge-list A→C, B→C, B→D, C→E, D→F, E→F — দুইটা একই জিনিস, শুধু লেখার ধরন আলাদা)

📌 Example — কীভাবে পড়বে B → [C, D] মানে B থেকে C এবং D — দুই জায়গাতেই edge আছে (B→C এবং B→D)। F → [] মানে F এর কোনো out-going edge নেই (F থেকে কোথাও যাওয়া যায় না)।

অংশ ২: Exam Definition (English)

📖 Exam Definition Topological Sort is a linear ordering of the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u comes before vertex v in the ordering.

Topological Sort is only possible for a DAG. If the graph contains a cycle, topological sort does not exist.

📌 Example আমাদের Main Example Graph এ, A→C edge আছে মানে final answer এ A অবশ্যই C এর আগে থাকতে হবে। এটাই definition এর মূল কথা।

অংশ ৩: Method 1 — DFS + Stack Algorithm

৩.১ Algorithm এর ধাপগুলো

একটা empty Stack নাও এবং সব node কে unvisited হিসেবে mark করো।
গ্রাফের যেকোনো unvisited node থেকে DFS শুরু করো।
DFS চলাকালীন, একটা node এর সব child সম্পূর্ণভাবে explore হয়ে গেলে — সেই node কে "finished" ধরা হয়, এবং সেটাকে Stack এ push করো।
যতক্ষণ পর্যন্ত সব node visited না হয়, ততক্ষণ ধাপ ২-৩ repeat করো (disconnected অংশের জন্য)।
সবশেষে, Stack এর উপর থেকে নিচে (top to bottom) পড়লেই Topological Order পাওয়া যাবে।

৩.২ প্রতিটা ধাপ কেন দরকার

কেন "finish" হলে push করি? কারণ node এর সব child explore শেষ হওয়ার মানে হলো তার অধীনে যা কিছু আছে সব শেষ। তাই stack এ রাখলে, উল্টো (top থেকে) পড়ার সময় সে তার child দের আগে চলে আসবে।
কেন Stack (Queue না)? কারণ সবার শেষে finish হওয়া node (root এর কাছের) — সেটাকে সবার প্রথমে আনতে হবে। Stack এর LIFO ধর্মের কারণে এটা সম্ভব।

অংশ ৪: Q1 সমাধান — DFS + Stack Method (Step-by-Step)

আমরা Main Example Graph এ DFS চালাবো, A থেকে শুরু করে।

Step	কী ঘটছে	Push হলো?	Stack (bottom → top)
1	A থেকে শুরু, A→C এ যাই	—	(empty)
2	C তে এলাম, C→E এ যাই	—	(empty)
3	E তে এলাম, E→F এ যাই	—	(empty)
4	F এর out-edge নেই → finish	F	`F`
5	ফিরে E তে, child শেষ → finish	E	`F, E`
6	ফিরে C তে, child শেষ → finish	C	`F, E, C`
7	ফিরে A তে, child শেষ → finish	A	`F, E, C, A`
8	নতুন unvisited node B থেকে শুরু, B→C (visited, skip)	—	`F, E, C, A`
9	B→D এ যাই (unvisited)	—	`F, E, C, A`
10	D→F (visited, skip), D এর child শেষ → finish	D	`F, E, C, A, D`
11	ফিরে B তে, child শেষ → finish	B	`F, E, C, A, D, B`

প্রতিটা ধাপের ব্যাখ্যা

Step 1-3: যতদূর সম্ভব গভীরে গেলাম (A→C→E→F) — এটাই DFS এর মূল ধর্ম।
Step 4: F এর কোনো out-going edge নেই, তাই F "finished" এবং push হলো। এরপর backtrack করে E তে ফিরবো।
Step 5-7: backtrack করতে করতে E, C, A সবাইকে finish করে push করলাম।
Step 8-9: A এর DFS tree শেষ। B এখনো unvisited, তাই নতুন DFS শুরু — গ্রাফে multiple disconnected অংশ থাকতে পারে বলে এটা জরুরি।
Step 10-11: D এবং তারপর B — দুইজনকেই finish করে push করলাম।

Stack (bottom → top): F, E, C, A, D, B — এখন top থেকে পড়তে হবে:

✅ Final Answer: Topological Order: B, D, A, C, E, F

Verification (Extra Marks এর জন্য অবশ্যই লিখবে)

Edge	Position Check	ঠিক আছে?
A→C	A(pos 3) আগে, C(pos 4) পরে	✓
B→C	B(pos 1) আগে, C(pos 4) পরে	✓
B→D	B(pos 1) আগে, D(pos 2) পরে	✓
C→E	C(pos 4) আগে, E(pos 5) পরে	✓
D→F	D(pos 2) আগে, F(pos 6) পরে	✓
E→F	E(pos 5) আগে, F(pos 6) পরে	✓

সব edge এর নিয়ম মানা হয়েছে ⇒ Answer সঠিক।

📝 Exam Script এ ঠিক এভাবে লিখবে (Model Answer)

উপরের সবটা শুধু বোঝার জন্য বিস্তারিত করে লেখা হয়েছে। খাতায় exam এ ঠিক এইরকম সংক্ষিপ্ত, পরিষ্কার আকারে লিখলেই full marks পাওয়া যায়।

Given: A directed acyclic graph with edges A→C, B→C, B→D, C→E, D→F, E→F.

Step 1 — Perform DFS starting from A (mark each vertex "finished" when all its outgoing edges are explored, and push it onto a stack):

Order Finished	1st	2nd	3rd	4th	5th	6th
Vertex	F	E	C	A	D	B

Step 2 — Stack after DFS (bottom → top): F, E, C, A, D, B

Step 3 — Read the stack from top to bottom to get the topological order.

Topological Order (DFS + Stack): B, D, A, C, E, F

Step 4 — Verify (for extra marks): Every edge u→v satisfies "u appears before v" — A before C, B before C, B before D, C before E, D before F, E before F. Hence verified. ✓

📌 Example (আরও সহজভাবে বুঝি) ভাবো তুমি Restaurant এ খাবার বানাচ্ছো — "রান্না শেষ করা" (F এর মতো) সবসময় "রান্না শুরু করা" (A/B এর মতো) এর পরে হবে। এখানে F সবসময় A এবং B এর পরে বসেছে, কারণ F সবচেয়ে বেশি dependency-র উপর নির্ভরশীল।

অংশ ৫: Method 2 — Kahn's Algorithm (In-degree Method)

৫.১ কেন আরেকটা Method শেখা দরকার?

DFS+Stack method ছাড়াও exam এ Kahn's Algorithm আসতে পারে। এটা সম্পূর্ণ আলাদা approach — DFS/Stack ব্যবহার না করে in-degree এবং Queue ব্যবহার করে।

৫.২ Algorithm এর ধাপগুলো

প্রতিটা node এর in-degree গণনা করো।
in-degree 0 যাদের, তাদের একটা Queue তে রাখো।
Queue থেকে node বের করো (dequeue), output list এ যোগ করো।
সেই node এর সব out-going edge "মুছে ফেলো" — তার child দের in-degree ১ করে কমাও।
কোনো node এর in-degree 0 হয়ে গেলে Queue তে যোগ করো।
Queue খালি না হওয়া পর্যন্ত ধাপ ৩-৫ repeat করো।
Cycle check: output size < V হলে — cycle আছে, sort সম্ভব না।

৫.৩ প্রতিটা ধাপ কেন দরকার

in-degree 0 কেন প্রথমে নিই? কারণ তার উপর কারো dependency নেই — তাই সবচেয়ে আগে "করা" যায়।
edge মুছে in-degree কমাই কেন? node process হয়ে গেলে, তার dependent দের একটা dependency পূরণ হয়ে গেলো। in-degree 0 হলে বুঝি সব dependency পূরণ।

📌 Example Main Example Graph এ A এবং B এর মধ্যে কোনো tree তে কোনো edge ঢুকছে না, তাই in-degree(A) = in-degree(B) = 0। এরাই Kahn's Algorithm এ সবার প্রথমে Queue তে ঢুকবে।

অংশ ৬: Q2 সমাধান — Kahn's Algorithm (Step-by-Step)

Initial In-degree: A=0, B=0, C=2 (A→C, B→C), D=1 (B→D), E=1 (C→E), F=2 (D→F, E→F)

Step	In-degree 0 (Queue তে যারা)	কাকে নিলাম	Update	Output
1	A, B	A	C: 2→1	A
2	B	B	C: 1→0, D: 1→0	A, B
3	C, D	C	E: 1→0	A, B, C
4	D, E	D	F: 2→1	A, B, C, D
5	E	E	F: 1→0	A, B, C, D, E
6	F	F	—	A, B, C, D, E, F

প্রতিটা ধাপের ব্যাখ্যা

Step 1: A, B — দুইজনেরই in-degree 0। A কে নিলাম। A→C মুছলাম, C: 2→1।
Step 2: B কে নিলাম। B→C, B→D মুছলাম। C: 1→0, D: 1→0 — দুইজনেই Queue তে ঢুকলো।
Step 3: C কে নিলাম। C→E মুছলাম, E: 1→0।
Step 4: D কে নিলাম। D→F মুছলাম, F: 2→1 (এখনো 0 না)।
Step 5: E কে নিলাম। E→F মুছলাম, F: 1→0।
Step 6: F কে নিলাম। কোনো out-edge নেই। Queue খালি, শেষ।

Cycle Check: Output size = 6 = V(6) ⇒ cycle নেই, valid answer।

✅ Final Answer: Kahn's Order: A, B, C, D, E, F

📝 Exam Script এ ঠিক এভাবে লিখবে (Model Answer)

উপরের সবটা শুধু বোঝার জন্য বিস্তারিত করে লেখা হয়েছে। খাতায় exam এ ঠিক এইরকম সংক্ষিপ্ত, পরিষ্কার আকারে লিখলেই full marks পাওয়া যায় — অতিরিক্ত ব্যাখ্যা লেখার দরকার নেই।

Given: A directed acyclic graph with edges A→C, B→C, B→D, C→E, D→F, E→F.

Step 1 — Find in-degree of every vertex:

Vertex	A	B	C	D	E	F
In-degree	0	0	2	1	1	2

Step 2 — Apply Kahn's Algorithm (process using a Queue):

Queue	Node Removed	In-degree Updated	Result so far
[A, B]	A	C: 2→1	A
[B]	B	C: 1→0, D: 1→0	A, B
[C, D]	C	E: 1→0	A, B, C
[D, E]	D	F: 2→1	A, B, C, D
[E]	E	F: 1→0	A, B, C, D, E
[F]	F	—	A, B, C, D, E, F

Step 3 — Check for cycle: Number of nodes in result = 6 = Total vertices (V = 6). So the graph has no cycle and the topological order is valid.

Topological Order (Kahn's Algorithm): A, B, C, D, E, F

Step 4 — Verify (optional, for extra marks): Every edge u→v satisfies "u appears before v" in the above order. Hence verified. ✓

অংশ ৬.৫: DFS vs Kahn's — কোনটা কখন ব্যবহার করবে (নতুন সংযোজন)

বিষয়	DFS + Stack Method	Kahn's Algorithm
ব্যবহৃত Data Structure	Stack (+ Recursion)	Queue
ভিত্তি	Node কবে "finish" হচ্ছে	Node এর in-degree কবে 0 হচ্ছে
Cycle Detection	Recursion stack এ পুনরায় node পাওয়া গেলে	শেষে output size < V হলে
Implementation	সাধারণত Recursive (তাই বুঝতে একটু কঠিন)	সাধারণত Iterative (তাই বুঝতে একটু সহজ)
কবে ব্যবহার সুবিধাজনক	Recursion-friendly প্রশ্নে	Level-by-level dependency বোঝাতে সুবিধাজনক

📌 Example লক্ষ্য করো — একই graph এ দুই method থেকে দুইটা ভিন্ন কিন্তু দুইটাই সঠিক answer এসেছে (B,D,A,C,E,F বনাম A,B,C,D,E,F)। Exam এ যে কোনো একটা method ব্যবহার করলেই চলবে, প্রশ্নে যদি নির্দিষ্ট method বলা না থাকে।

অংশ ৭: Q3 সমাধান — একাধিক Answer কি Valid?

প্রশ্ন: DFS method দিয়ে পেলাম B, D, A, C, E, F আর Kahn's method দিয়ে পেলাম A, B, C, D, E, F — দুইটা আলাদা answer, তাহলে কি দুইটাই ঠিক?

উত্তর: হ্যাঁ, দুইটাই সঠিক।

কেন? একটা DAG এর একাধিক valid topological order থাকতে পারে, যদি এমন কিছু node pair থাকে যাদের মধ্যে কোনো সরাসরি বা পরোক্ষ dependency নেই। এখানে A এবং B এর মধ্যে কোনো edge নেই, তাই কখনো A আগে, কখনো B আগে আসতে পারে — দুইটাই ঠিক, যতক্ষণ সব edge এর নিয়ম মানা হচ্ছে।

📌 Example ভাবো তোমার দুইটা independent কাজ আছে — "কাপড় ধোয়া" আর "বাজার করা"। এই দুইটার মধ্যে কোনো সম্পর্ক নেই, তাই তুমি যেকোনো order এ করতে পারো — দুইটাই সঠিক। ঠিক একইভাবে A, B independent বলে দুই method এ দুই রকম (কিন্তু দুইটাই valid) order এসেছে।

খাতায় লিখে দাও "A DAG may have more than one valid topological order. This answer satisfies all edge constraints, hence it is valid."

📝 Exam Script এ ঠিক এভাবে লিখবে (Model Answer)

এই ধরনের "ব্যাখ্যা করো" প্রশ্নে বেশি লেখার দরকার নেই — যুক্তি + একটা উদাহরণ + সিদ্ধান্ত, এই তিনটাই যথেষ্ট।

Answer: Yes, both orderings are valid.

Reason: A DAG can have more than one valid topological order whenever two or more vertices are independent of each other (no direct or indirect dependency between them).

Justification with this graph: Vertices A and B have no edge between them, so their relative position can vary. Both B, D, A, C, E, F (from DFS) and A, B, C, D, E, F (from Kahn's) satisfy every edge constraint (A→C, B→C, B→D, C→E, D→F, E→F).

Conclusion: A DAG may have more than one valid topological order, and any ordering that satisfies all edge constraints is correct.

অংশ ৮: Q4 সমাধান — Cycle থাকলে কী হবে?

DFS Method এ Cycle Detect: DFS করার সময় যদি এমন কোনো node এ পৌঁছাই যেটা বর্তমানে recursion stack এ আছে (তার DFS এখনো শেষ হয়নি) — তাহলে বুঝতে হবে একটা back edge পাওয়া গেছে, যেটা মানে cycle আছে।

Kahn's Method এ Cycle Detect: Algorithm শেষে output size < V হলে — কিছু node এর in-degree কখনো 0 হয়নি (একে অপরের উপর নির্ভরশীল, cycle এ আটকে আছে)।

📌 Example X→Y→Z→X গ্রাফে Kahn's Algorithm চালালে দেখবে X, Y, Z — কারো in-degree ই কখনো 0 হবে না। Queue শুরুতেই খালি, output size = 0 < V(3)। তাই cycle আছে, sort সম্ভব না।

            X
          ╱   ▲
        ▼       ╲
       Y  ─────►  Z

Cycle Example (পুনরায়)

✅ Final Answer: If a cycle exists in the graph, Topological Sort is not possible.

Time Complexity (দুই method এই একই): O(V + E) — প্রতিটা vertex এবং edge ঠিক একবার করে visit/process করা হয় বলে।

📝 Exam Script এ ঠিক এভাবে লিখবে (Model Answer)

"Cycle থাকলে কী হবে" টাইপ প্রশ্নে দুই method এর detection rule + এক লাইনের conclusion লিখলেই মার্কস পাওয়া যায়।

Given: Graph with edges X→Y, Y→Z, Z→X.

DFS-based detection: While performing DFS, if we reach a vertex that is already present in the current recursion stack (i.e., still being processed), a back edge is found, which indicates a cycle. Here, Z→X is a back edge since X is still in the recursion stack when Z is visited.

Kahn's-based detection: Applying Kahn's Algorithm, the in-degree of X, Y, and Z never becomes 0 (each has exactly one incoming edge from within the cycle), so the queue remains empty from the start. Result size = 0, but V = 3, so 0 < V confirms a cycle.

Conclusion: Since the graph contains a cycle (X→Y→Z→X), topological sort is not possible.

অংশ ৯: সাধারণ ভুলগুলো (Common Mistakes)

DFS finish হওয়ার আগেই push করে ফেলা — node এর সব child শেষ হওয়ার পরেই push করতে হবে।
Stack কে bottom থেকে পড়া — সবসময় top থেকে পড়তে হবে।
Disconnected graph এ শুধু একটা node থেকে DFS চালানো — সব node visited না হলে, নতুন unvisited node থেকে আবার DFS শুরু করতে হবে।
Cycle থাকা সত্ত্বেও answer বের করার চেষ্টা করা — আগে cycle চেক করো।
in-degree ভুল গণনা করা — প্রতিটা edge u→v এর জন্য শুধু v এর in-degree বাড়বে, u এর না।
একটামাত্র answer কেই সঠিক মনে করা — verification table দিয়ে যাচাই করো, মিললেই তোমার answer সঠিক।
Verification step বাদ দেওয়া — extra marks এর জন্য অবশ্যই edge-by-edge verification table বানাও।

📌 Example (mistake #3 বোঝার জন্য) ধরো graph এ A→B এবং আলাদাভাবে C→D আছে (একে অপরের সাথে সংযোগহীন)। শুধু A থেকে DFS শুরু করে থেমে গেলে C, D কখনো visit হবে না, আর topological order অসম্পূর্ণ থেকে যাবে।

অংশ ৯.৫: Exam এ Full Marks পাওয়ার Answer-Writing কৌশল (নতুন সংযোজন)

প্রথমে Definition লিখো (English এ) — 1 mark সাধারণত এখানেই থাকে।
Diagram আঁকো — যদি graph টা edge-list আকারে দেওয়া থাকে, আগে সেটাকে ছবি এঁকে নাও, তাহলে ভুল হওয়ার সম্ভাবনা কমে।
Step-by-step table বানাও — শুধু final answer লিখলে full marks পাওয়া কঠিন। প্রতিটা step দেখাও।
Final Answer আলাদা করে বক্স/underline করে লেখো — examiner সহজে খুঁজে পাবে।
Verification table দাও — এটা প্রায়ই "extra marks" বা "correctness proof" হিসেবে চাওয়া হয়।
Multiple valid answer হতে পারে সেটা এক লাইনে উল্লেখ করো, যদি তোমার answer বইয়ের answer থেকে আলাদা হয়।

অংশ ১০: Practice Questions (ঠিক যেভাবে Exam-এ আসবে)

নিচের প্রশ্নগুলো হুবহু exam paper এর ফরম্যাটে লেখা হলো — তারকা (★) দিয়ে গুরুত্ব, marks বণ্টন, এবং sub-question (a, b, c) সহ। খেয়াল করো — কোনো graph কে আগে থেকেই "disconnected" বা অন্য কোনো ইঙ্গিত দেওয়া হয়নি; exam এ তোমাকেই সেটা লক্ষ্য করে নিতে হবে।

নিচের directed graph টি দেওয়া হলো:

  A ──► B
  A ──► C
  B ──► D
  C ──► D
  D ──► E

(a) প্রতিটি node এর in-degree বের করো। 2 marks
(b) DFS + Stack পদ্ধতিতে topological order নির্ণয় করো। প্রতিটি step দেখাও। 6 marks
(c) edge-by-edge verification table দিয়ে তোমার answer যাচাই করো। 2 marks

💡 Hint (উত্তর নয়)

A থেকে শুরু করো। লক্ষ্য করো B ও C দুইজনেই D এর আগে আসতে হবে, কিন্তু B ও C এর মধ্যে কোনো নির্দিষ্ট order নেই।

নিচের directed graph টি দেওয়া হলো (node গুলো সংখ্যা দিয়ে চিহ্নিত):

  1 ──► 2      1 ──► 3
  2 ──► 4      3 ──► 4
  4 ──► 5      3 ──► 5

(a) Kahn's Algorithm ব্যবহার করে সম্পূর্ণ in-degree table বানাও এবং প্রতিটি step দেখাও। 6 marks
(b) চূড়ান্ত Topological Order লিখো। 2 marks

নিচের directed graph টি একজন ছাত্র বিশ্লেষণ করছে:

  X ──► Y
  Y ──► Z
  Z ──► X

(a) এই গ্রাফে কি Topological Sort সম্ভব? উত্তরের পক্ষে কারণ দাও। 3 marks
(b) DFS পদ্ধতি এবং Kahn's Algorithm — দুইটা পদ্ধতিতেই কীভাবে এই সমস্যা (যদি থাকে) শনাক্ত করা যায়, তা আলাদাভাবে ব্যাখ্যা করো। 3 marks

নিচের directed graph টি দেওয়া হলো:

  P ──► Q      P ──► R
  Q ──► S      R ──► S
  S ──► T      R ──► T

(a) DFS + Stack পদ্ধতিতে একটি Topological Order বের করো। 4 marks
(b) Kahn's Algorithm দিয়ে আরেকটি Topological Order বের করো। 4 marks
(c) দুইটি answer যদি ভিন্ন হয়, ব্যাখ্যা করো কেন দুইটিই সঠিক হতে পারে (অথবা কেন same answer এসেছে)। 2 marks

নিচের directed graph টি একটি সফটওয়্যার প্রজেক্টের টাস্ক-ডিপেন্ডেন্সি দেখাচ্ছে:

  A ──► B
  C ──► D
  D ──► E

(a) গ্রাফটি ভালোভাবে পর্যবেক্ষণ করো — এটি কি একটি single connected গ্রাফ, নাকি একাধিক আলাদা অংশে বিভক্ত? ব্যাখ্যা করো। 2 marks
(b) DFS + Stack পদ্ধতিতে সম্পূর্ণ Topological Order বের করো। প্রতিটি node কীভাবে এবং কখন visit করা হচ্ছে তা step-by-step দেখাও — বিশেষভাবে খেয়াল রাখো, একটি DFS run দিয়ে যদি সব node cover না হয়, তাহলে কী করতে হবে। 7 marks
(c) edge-by-edge verification table দিয়ে যাচাই করো। 3 marks

💡 Hint (উত্তর নয়)

একবার A থেকে DFS চালানোর পর, তুমি কি B এর বাইরে আর কোনো node visit করতে পারছো? যদি না পারো, তাহলে বাকি node গুলোর কী হবে?

Quick Revision Summary

কোথায় কাজ করে	শুধু DAG এ (Directed + Acyclic)
Directed edge	একদিকমুখী সম্পর্ক (Math-1 → Math-2 → Physics)
Cycle	ঘুরে ফিরে একই node এ আসা (X→Y→Z→X)
In-degree	কতগুলো edge ঢুকছে (A→C, B→C হলে in-degree(C)=2)
Adjacency List	প্রতিটা node এর "children" লিস্ট আকারে (B → [C, D])
Method 1 (DFS+Stack)	Finish হলে push → top থেকে পড়ো (Q1 উদাহরণ: B, D, A, C, E, F)
Method 2 (Kahn's)	in-degree 0 → Queue → output → in-degree কমাও (Q2 উদাহরণ: A, B, C, D, E, F)
Cycle detection (DFS)	recursion stack এ থাকা node এ আবার পৌঁছালে cycle
Cycle detection (Kahn's)	output size < V হলে cycle
একাধিক answer	independent node থাকলে একাধিক valid order সম্ভব
Time Complexity	O(V + E) — দুই method এই