Bird
Raised Fist0

Consider a graph with 4 courses and prerequisites [[1,0],[2,0],[3,1],[3,2]]. Using Kahn's Algorithm, which of the following is a valid order to complete all courses?

easy🧾 Trace Q3 of Q15
Topological Sort - Course Schedule II (Topological Order)
Consider a graph with 4 courses and prerequisites [[1,0],[2,0],[3,1],[3,2]]. Using Kahn's Algorithm, which of the following is a valid order to complete all courses?
A[0, 1, 2, 3]
B[0, 2, 1, 3]
C[1, 0, 2, 3]
D[3, 1, 2, 0]
Step-by-Step Solution
Solution:
  1. Step 1: Calculate in-degree for each course

    Course 0 has in-degree 0, courses 1 and 2 have in-degree 1, course 3 has in-degree 2.
  2. Step 2: Initialize queue with courses having in-degree 0

    Start with course 0.
  3. Step 3: Process queue and update in-degree

    Remove 0, reduce in-degree of 1 and 2 to 0, add them to queue. Then remove 2 and 1, reduce in-degree of 3 to 0, add 3.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    All prerequisites appear before dependent courses [OK]
Quick Trick: Start with zero in-degree nodes and process dependencies [OK]
Common Mistakes:
MISTAKES
  • Ignoring the order of prerequisites
  • Starting with a course that has prerequisites
  • Not updating in-degree after removing nodes
Trap Explanation:
PITFALL
  • Option A and C start with courses that have prerequisites, which is invalid.
Interviewer Note:
CONTEXT
  • Tests understanding of Kahn's Algorithm and topological ordering.
Master "Course Schedule II (Topological Order)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes