Graph Traversal: Solving the 'Course Schedule' Problem

Graph traversal questions come up frequently in coding interviews, and the LeetCode 'Course Schedule' problem is a great example. At its core, this problem asks us to figure out whether it's possible to complete a series of courses given specific dependencies between them. In practical terms, we need to detect if there are cycles in a graph of course dependencies.

In this article, I intend to break down the problem, explain why it's essentially a graph traversal challenge, and walk through a clear solution step‑by‑step using TypeScript.

What's the 'Course Schedule' Problem Actually About?

The 'Course Schedule' problem (LeetCode #207) essentially asks us to figure out whether we can complete all courses, given a list of prerequisites. Each course might depend on another course being finished first.

Simple Example

Imagine we have four courses numbered from 0 to 3, with these prerequisites:

numCourses = 4;prerequisites = [[1, 0], [2, 1], [3, 2]];

This means that:

• You need to finish course 0 before starting course 1.
• Course 1 must be completed before course 2.
• Course 2 must be completed before course 3.

In this situation, there's clearly a logical path through the courses, like this:

0 → 1 → 2 → 3

Because this is a straightforward chain without loops, it is possible to complete all four courses in order.

Example of a More Problematic Case

Now, imagine a slightly different scenario:

numCourses = 2;prerequisites = [[1, 0], [0, 1]];

Here, we have:

• Course 0 requires course 1 to be completed first.
• Course 1 requires course 0 to be completed first.

In this scenario, the dependencies form a cycle:

0 → 1 → 0

Because each course indirectly depends upon itself, neither course can be completed. In this problem, our job is to detect these scenarios quickly.

Why is This a Graph Problem?

Each course can be viewed as a node in a graph, and the dependencies become directed edges pointing from one node (course) to another. Detecting if it is possible to complete all courses now becomes about finding cycles in a directed graph.

If a cycle exists, we simply cannot finish all the courses, it's as straightforward as that.

Solving the Problem Using Depth‑First Search (Dfs)

One efficient way to detect cycles is using Depth‑First Search (DFS). Here's how we might approach this practically using JavaScript:

Step‑By‑Step Solution

1. Create an adjacency list to represent the graph of courses.
2. Traverse each node using DFS.
3. Keep track of visited nodes and nodes currently in the recursion stack.
4. We know we have found a cycle if we revisit a node already in the recursion stack.

A JavaScript/TypeScript might look something like this:

const canFinish = (numCourses: number, prerequisites: number[][]): boolean => {  const graph = Array.from({ length: numCourses }, () => [] as number[]);  const visited = new Set<number>();  const recStack = new Set<number>();  prerequisites.forEach(([course, pre]) => {    graph[pre].push(course);  });  const hasCycle = (course: number): boolean => {    if (recStack.has(course)) return true;    if (visited.has(course)) return false;    visited.add(course);    recStack.add(course);    for (const neighbour of graph[course]) {      if (hasCycle(neighbour)) return true;    }    recStack.delete(course);    return false;  };  for (let i = 0; i < numCourses; i++) {    if (!visited.has(i) && hasCycle(i)) {      return false;  // cycle detected    }    visited.add(i);  }  return true;  // no cycles found};

Why Does This Work?

• We know that if we encounter a node that is already in our recursion stack, then we have found a cycle.
• If we manage to traverse all of the nodes without encountering this, then the courses are safe to complete.

Adding Tests for Reliability

When it comes to tests like this, if you have been assigned it as part of an interview or technical assessment, then adding test coverage might just offer you an extra bit of credit. Testing is always important to ensure that our functions work in all scenarios and edge cases. It is trivially straightforward to add Jest coverage for our canFinish function:

test('detects no cycle correctly', () => {  expect(canFinish(2, [[1, 0]])).toBe(true);});test('detects cycle correctly', () => {  expect(canFinish(2, [[1, 0], [0, 1]])).toBe(false);});

With these tests, you can quickly confirm that our function behaves as intended, catching potential issues early. This is especially handy if whomever has set this task for you has provided a list of example inputs and expected outputs.

Common Mistakes to Avoid

Not Marking Visited Nodes Properly

Forgetting to mark nodes as visited can lead to incorrect cycle detection. Ensure you carefully track each node you've processed.

Confusing Recursion and Visited States

Clearly distinguish between nodes currently in the recursion stack and nodes that have been fully processed. Mixing these states up can produce false positives.

Practical Tips for Graph Problems

• Draw diagrams to visualise the graph structure; this greatly helps in understanding the traversal your function needs to follow clearly.
• Keep track of node states explicitly and consistently.
• Always test for both positive and negative cases (with and without cycles).

Wrapping up

The 'Course Schedule' problem is really about understanding how graphs and cycles work. By carefully applying a depth‑first search, we can quickly determine if course dependencies are solvable or if they're circular and impossible. Knowing how to tackle these types of problems not only helps in technical interviews but also sharpens our general coding skills.

Key Takeaways

• The Course Schedule problem checks for cycles within graph structures.
• Using DFS and tracking nodes carefully allows quick detection of cycles.
• Testing is crucial to ensure the solution correctly identifies cycles and non‑cycles.
• Clearly tracking visited and recursion states prevents mistakes.

With this understanding, graph traversal becomes much less intimidating and can even become an enjoyable part of your coding practice.