I've been thinking about how we track prerequisites for our course modules. Right now, it's just a list, but in reality, learning is a graph. To learn "Advanced Design Patterns," you might need "OOP Basics" and "SOLID Principles," and "SOLID" itself requires "OOP Basics." If we want to programmatically figure out a learning path, a simple array won't cut it. We need a Graph.

Mapping the dependencies

I'll start by sketching out a simple adjacency list. In PHP, the easiest way to represent a graph is an associative array where the keys are our nodes and the values are arrays of the nodes they connect to. Let's try this:

$graph = [
    'Logic' => ['Basic Math'],
    'Basic Math' => [],
    'JavaScript' => ['Logic'],
    'React' => ['JavaScript', 'HTML/CSS'],
    'HTML/CSS' => ['Basic Math'],
    'Next.js' => ['React'],
];

It looks fine on paper, but if I want to find every single thing I need to know before I touch Next.js, I can't just look at the 'Next.js' key. I have to follow the chain. This is where traversal comes in. I'm going to try a Depth-First Search (DFS) first, because it feels natural to just "dive deep" into one prerequisite before moving to the next.

Falling down the rabbit hole with DFS

I'll write a recursive function. The idea is: start at a node, visit its first neighbor, then that neighbor's neighbor, and so on, until I hit a dead end.

function dfs($graph, $node, &$visited = []) {
    if (in_array($node, $visited)) return;

    echo "Visiting: $node\n";
    $visited[] = $node;

    foreach ($graph[$node] as $neighbor) {
        dfs($graph, $neighbor, $visited);
    }
}

dfs($graph, 'Next.js');

Running this, I see: Next.js → React → JavaScript → Logic → Basic Math. Then it backtracks to HTML/CSS → Basic Math. Wait, it visited Basic Math twice. That's why I added the $visited array—without it, if I had a circular dependency (like A depends on B, and B depends on A), this script would crash my server with a stack overflow. Always track where you've been.

Switching gears to BFS

DFS is great for finding the "bottom" of a dependency chain, but what if I want to know the shortest path? Or maybe I just want to see the immediate layers of requirements? For that, DFS is the wrong tool. I need Breadth-First Search (BFS). Instead of diving deep, BFS explores all immediate neighbors first.

I can't use recursion easily for BFS. I need a queue. PHP has SplQueue, which is much more efficient than using array_shift() on a standard array (which re-indexes the whole array every time). Let's see if we can implement this.

function bfs($graph, $startNode) {
    $queue = new SplQueue();
    $queue->enqueue($startNode);
    $visited = [$startNode => true];

    while (!$queue->isEmpty()) {
        $currentNode = $queue->dequeue();
        echo "Exploring: $currentNode\n";

        foreach ($graph[$currentNode] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue->enqueue($neighbor);
            }
        }
    }
}

bfs($graph, 'Next.js');

Now the output changes. It hits Next.js, then React, then it hits JavaScript and HTML/CSS before it ever touches Logic. It's moving in ripples. If this were a social network, BFS would be how you find "friends of friends" or the shortest distance between two people.

When to use which?

After playing with both, the distinction is clear to me. If I'm trying to solve a puzzle or find a path to a leaf node (like "what is the very first thing I need to learn?"), DFS is my go-to. If I'm looking for the closest target or scanning a neighborhood, BFS is the winner. The key implementation difference is simply the data structure: DFS uses a Stack (implicitly via recursion), and BFS uses a Queue.

📋 Practical Task

Building a Movie Recommendation Path-Finder

You are building a feature for a movie app. Movies are nodes in a graph, and an edge exists between two movies if they share the same director or lead actor. Your goal is to find the "degrees of separation" between two movies.

The Task: Implement a function findShortestPath($graph, $start, $target) using a Breadth-First Search. Instead of just visiting nodes, your function must keep track of the path taken.

Requirements:

• Use an adjacency list (associative array) to represent the movie connections.
• Use SplQueue for the traversal.
• The function should return an array representing the shortest path from the start movie to the target movie (e.g., ['Inception', 'Interstellar', 'The Prestige']).
• If no path exists, return null.

Starter Graph:

$movieGraph = [
    'Inception' => ['Interstellar', 'The Dark Knight'],
    'Interstellar' => ['Inception', 'The Prestige'],
    'The Dark Knight' => ['Inception', 'Batman Begins'],
    'The Prestige' => ['Interstellar', 'Tenet'],
    'Batman Begins' => ['The Dark Knight'],
    'Tenet' => ['The Prestige'],
];