Breadth-First Search (BFS) is a fundamental algorithm in computer science used for exploring graphs and trees level by level. Unlike Depth-First Search, which dives deep into a branch before backtracking, BFS starts at a given node and visits all its neighbors first before moving to the next level. This makes BFS particularly useful for finding the shortest path in unweighted graphs, solving puzzles, and exploring hierarchical structures systematically.
with hands-on learning.
get the skills and confidence to land your next move.
BFS is widely used in real-world applications such as social network analysis, pathfinding in maps, AI algorithms, and network broadcasting. Learning BFS in PHP gives beginners practical experience in working with queues, managing visited nodes, and traversing complex data structures. By understanding BFS, beginners build a strong foundation for more advanced graph algorithms like Dijkstra’s shortest path and level-order tree traversal.
Program 1: BFS Using a Queue on an Adjacency List
This program demonstrates a classic BFS traversal using a queue on a simple graph represented by an adjacency list.
<?php
function bfs($graph, $start) {
$visited = [];
$queue = [$start];
$visited[$start] = true;
while (!empty($queue)) {
$node = array_shift($queue);
echo $node . " ";
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue[] = $neighbor;
}
}
}
}
$graph = [
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
];
echo "BFS Traversal: ";
bfs($graph, 'A');
?>This program uses a queue to manage nodes at the current level before moving to the next level. The visited array ensures nodes are not revisited, preventing infinite loops. Beginners can see how BFS systematically explores each level of a graph, which is different from DFS’s depth-first approach.
Program 2: BFS to Find Shortest Path
This program shows how BFS can be used to find the shortest path from a source node to a target node in an unweighted graph.
<?php
function bfsShortestPath($graph, $start, $target) {
$visited = [];
$queue = [[$start]];
$visited[$start] = true;
while (!empty($queue)) {
$path = array_shift($queue);
$node = end($path);
if ($node == $target) return $path;
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$newPath = $path;
$newPath[] = $neighbor;
$queue[] = $newPath;
}
}
}
return [];
}
$graph = [
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
];
$path = bfsShortestPath($graph, 'A', 'F');
if (!empty($path)) echo "Shortest path from A to F: " . implode(" -> ", $path);
else echo "No path found from A to F.";
?>By storing paths in the queue, this program finds the shortest route efficiently. Beginners can understand how BFS naturally explores level by level, ensuring the first path found is the shortest in an unweighted graph.
Program 3: BFS Using Recursion (Simulated with Queue)
While BFS is traditionally iterative, it can be implemented recursively by processing nodes in a queue structure.
<?php
function bfsRecursive($graph, &$queue, &$visited) {
if (empty($queue)) return;
$node = array_shift($queue);
echo $node . " ";
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue[] = $neighbor;
}
}
bfsRecursive($graph, $queue, $visited);
}
$graph = [
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
];
$queue = ['A'];
$visited = ['A' => true];
echo "BFS Traversal (Recursive): ";
bfsRecursive($graph, $queue, $visited);
?>This approach demonstrates how recursion can be combined with a queue to simulate BFS. Beginners can learn both recursion and queue management while understanding BFS traversal principles.
Program 4: BFS for Weighted Graph (Ignoring Weights for Traversal)
This program adapts BFS to a weighted graph, where traversal ignores weights but can print them for reference.
<?php
function bfsWeighted($graph, $start) {
$visited = [];
$queue = [$start];
$visited[$start] = true;
while (!empty($queue)) {
$node = array_shift($queue);
echo $node . " ";
foreach ($graph[$node] as $neighbor => $weight) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
echo "(weight: $weight) ";
$queue[] = $neighbor;
}
}
}
}
$graph = [
'A' => ['B' => 2, 'C' => 3],
'B' => ['D' => 4, 'E' => 5],
'C' => ['F' => 6],
'D' => [],
'E' => ['F' => 1],
'F' => []
];
echo "BFS Traversal with Weights: ";
bfsWeighted($graph, 'A');
?>Weighted BFS helps beginners see how to adapt BFS to more complex graphs while still maintaining its level-by-level traversal.
Program 5: BFS to Count Levels in a Graph
This program shows how BFS can be used to determine the number of levels (or layers) from a starting node in a graph.
<?php
function bfsLevels($graph, $start) {
$visited = [];
$queue = [$start];
$visited[$start] = true;
$level = 0;
while (!empty($queue)) {
$levelSize = count($queue);
echo "Level $level: ";
for ($i = 0; $i < $levelSize; $i++) {
$node = array_shift($queue);
echo $node . " ";
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue[] = $neighbor;
}
}
}
echo "\n";
$level++;
}
}
$graph = [
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
];
echo "BFS Levels:\n";
bfsLevels($graph, 'A');
?>This example shows BFS’s natural ability to explore a graph level by level. Beginners can see how queues and iteration work together to organize traversal and determine depth information.
Frequently Asked Questions (FAQ)
BFS is widely used, but beginners often have questions about its implementation and applications.
Q1: When should I use BFS?
BFS is ideal for finding the shortest path in unweighted graphs and exploring nodes level by level.
Q2: How is BFS different from DFS?
BFS explores neighbors first before going deeper, while DFS explores one branch fully before backtracking.
Q3: Can BFS handle cycles?
Yes, by marking visited nodes, BFS avoids revisiting and infinite loops.
Q4: Is BFS recursive or iterative?
BFS is typically implemented iteratively using a queue, though recursion can simulate it.
Q5: How is BFS applied in real-world scenarios?
BFS is used in network broadcasting, social network analysis, AI pathfinding, and level-order tree traversal.
Conclusion
Breadth-First Search is a powerful algorithm for traversing graphs and trees level by level. The PHP examples—covering basic traversal, shortest path, recursion simulation, weighted graphs, and level counting—show BFS’s versatility and practicality. By practicing BFS, beginners learn to manage queues, track visited nodes, and explore graph structures systematically. Mastering BFS lays the foundation for advanced graph algorithms and real-world problem-solving in PHP.
