🔍 BFS - Breadth First Search

🟢 BeginnerGraph Traversal

📋 What is BFS?

BFS explores a graph level by level, visiting all nodes at distance k before nodes at distance k+1. It uses a Queue (FIFO) and guarantees the shortest path in unweighted graphs.

🧠 Real-Life Analogy

Like ripples in water - you explore outward from the source, one layer at a time. Or like searching for a friend at a party: you check the current room first, then adjacent rooms, then further away.

💻 PHP Implementation

<?php
function bfs(array $graph, int $start): array {
    $visited = [$start => true];
    $queue = [$start];
    $result = [];

    while (!empty($queue)) {
        $node = array_shift($queue); // Dequeue (front)
        $result[] = $node;

        foreach ($graph[$node] ?? [] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = $neighbor; // Enqueue (rear)
            }
        }
    }
    return $result;
}

// Shortest path using BFS (unweighted graph)
function bfsShortestPath(array $graph, int $start, int $target): array {
    $visited = [$start => true];
    $parent = [$start => null]; // Track path
    $queue = [$start];

    while (!empty($queue)) {
        $node = array_shift($queue);
        if ($node === $target) {
            // Reconstruct path
            $path = [];
            while ($node !== null) {
                $path[] = $node;
                $node = $parent[$node];
            }
            return array_reverse($path);
        }
        foreach ($graph[$node] ?? [] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $parent[$neighbor] = $node;
                $queue[] = $neighbor;
            }
        }
    }
    return []; // No path found
}

// Example graph (adjacency list)
$graph = [
    0 => [1, 2],
    1 => [0, 3, 4],
    2 => [0, 5],
    3 => [1],
    4 => [1, 5],
    5 => [2, 4]
];

echo "BFS from 0: ";
print_r(bfs($graph, 0)); // [0,1,2,3,4,5]

echo "Shortest path 0→5: ";
print_r(bfsShortestPath($graph, 0, 5)); // [0,2,5]

📝 Dry Run

Graph: 0--1--3
       |  |
       2  4--5

BFS from node 0:
Queue: [0]
Pop 0 → enqueue neighbors 1,2 → Queue: [1,2]
Pop 1 → enqueue neighbors 3,4 (0 visited) → Queue: [2,3,4]
Pop 2 → enqueue 5 (0 visited) → Queue: [3,4,5]
Pop 3 → no new → [4,5]
Pop 4 → 5 already in queue → [5]
Pop 5 → no new → []
Result: [0,1,2,3,4,5] ✅

📊 Complexity

Time	O(V + E)	Visit each vertex & edge once
Space	O(V)	Queue + visited array

🌍 Applications

Shortest Path in unweighted graphs
Web Crawling: Explore links level by level
Social Networks: Find connections within k degrees
GPS Navigation: Find route with fewest turns
Puzzle Solving: Minimum moves in sliding puzzles

💼 Interview Questions

BFS when you need: shortest path, level-order, closer nodes first, or the graph is wide. DFS when you need: path existence, topological sort, deep exploration, or memory is tight.

Process queue level by level: get queue size, process exactly that many items. Or store (node, level) pairs. For shortest path, store distance array alongside BFS.

All Graph Algorithms Next: DFS