Depth-First Search (DFS) is one of the fundamental algorithms in computer science for exploring graphs and trees. It starts at a given node and explores as far as possible along each branch before backtracking. This makes DFS particularly useful for solving problems like finding paths, checking connectivity, or traversing hierarchical structures. Understanding DFS is a key skill for beginners who want to grasp how algorithms navigate complex data structures efficiently.
with hands-on learning.
get the skills and confidence to land your next move.
In practical scenarios, DFS is used in social networks to explore connections, in AI for solving puzzles, in file system traversal, and in network analysis. Learning DFS in PHP is a great way to combine algorithmic thinking with practical coding. By implementing DFS yourself, you’ll understand recursion, stacks, and graph representation, all while improving problem-solving skills.
Program 1: DFS Using Recursion on an Adjacency List
This program demonstrates the classic recursive approach to DFS on a simple graph represented with an adjacency list.
<?php
function dfsRecursive($graph, $node, &$visited) {
$visited[$node] = true;
echo $node . " ";
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) {
dfsRecursive($graph, $neighbor, $visited);
}
}
}
$graph = [
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
];
$visited = [];
echo "DFS Traversal: ";
dfsRecursive($graph, 'A', $visited);
?>In this program, the function recursively visits each node and explores its neighbors. The visited array prevents revisiting nodes, avoiding infinite loops. Beginners can see how recursion naturally handles the depth-first approach, exploring one branch fully before moving to the next.
Program 2: DFS Using Iteration with a Stack
This program implements DFS without recursion, using an explicit stack to manage traversal.
<?php
function dfsIterative($graph, $start) {
$visited = [];
$stack = [$start];
while (!empty($stack)) {
$node = array_pop($stack);
if (!isset($visited[$node])) {
echo $node . " ";
$visited[$node] = true;
foreach (array_reverse($graph[$node]) as $neighbor) {
if (!isset($visited[$neighbor])) $stack[] = $neighbor;
}
}
}
}
$graph = [
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
];
echo "DFS Traversal (Iterative): ";
dfsIterative($graph, 'A');
?>Using a stack explicitly simulates the recursion process. This iterative method is useful for avoiding stack overflow in large graphs. Beginners learn how DFS can be implemented both recursively and iteratively, giving flexibility in approach.
Program 3: DFS to Detect a Path Between Two Nodes
This program shows how DFS can be used to check if there is a path from a source node to a target node.
<?php
function dfsPath($graph, $current, $target, &$visited) {
if ($current == $target) return true;
$visited[$current] = true;
foreach ($graph[$current] as $neighbor) {
if (!isset($visited[$neighbor]) && dfsPath($graph, $neighbor, $target, $visited)) {
return true;
}
}
return false;
}
$graph = [
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
];
$visited = [];
$start = 'A';
$end = 'F';
if (dfsPath($graph, $start, $end, $visited)) echo "Path exists from $start to $end.";
else echo "No path exists from $start to $end.";
?>This example highlights how DFS can solve practical problems like path detection. The recursion explores possible routes until the target is found, showing beginners how traversal can be used in decision-making and problem-solving.
Program 4: DFS on a Weighted Graph (Adjacency List)
This program adapts DFS to handle weighted graphs, printing nodes along with edge weights.
<?php
function dfsWeighted($graph, $node, &$visited) {
$visited[$node] = true;
echo $node . " ";
foreach ($graph[$node] as $neighbor => $weight) {
if (!isset($visited[$neighbor])) {
echo "(weight: $weight) ";
dfsWeighted($graph, $neighbor, $visited);
}
}
}
$graph = [
'A' => ['B' => 2, 'C' => 3],
'B' => ['D' => 4, 'E' => 5],
'C' => ['F' => 6],
'D' => [],
'E' => ['F' => 1],
'F' => []
];
$visited = [];
echo "DFS Traversal with Weights: ";
dfsWeighted($graph, 'A', $visited);
?>Weighted DFS is helpful when analyzing networks or cost-based traversal. Beginners can see how DFS can adapt to more complex graphs while maintaining the depth-first approach.
Program 5: DFS to Count Connected Components
This program uses DFS to count the number of connected components in an undirected graph.
<?php
function dfsComponent($graph, $node, &$visited) {
$visited[$node] = true;
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) dfsComponent($graph, $neighbor, $visited);
}
}
$graph = [
'A' => ['B'],
'B' => ['A', 'C'],
'C' => ['B'],
'D' => ['E'],
'E' => ['D'],
'F' => []
];
$visited = [];
$components = 0;
foreach ($graph as $node => $neighbors) {
if (!isset($visited[$node])) {
dfsComponent($graph, $node, $visited);
$components++;
}
}
echo "Number of connected components: $components";
?>This shows a practical application of DFS in network analysis. Each DFS traversal explores one component, helping beginners understand how DFS can identify clusters in a graph.
Frequently Asked Questions (FAQ)
DFS is versatile, but beginners often have questions about its implementation and use.
Q1: What is DFS used for?
DFS is used to explore graphs, find paths, detect cycles, and traverse hierarchical structures like trees and file systems.
Q2: How does DFS differ from BFS?
DFS explores one branch fully before backtracking, while BFS explores all neighbors level by level.
Q3: Can DFS handle cycles in a graph?
Yes, by keeping a visited array or set, DFS avoids infinite loops caused by cycles.
Q4: Is DFS recursive or iterative?
It can be implemented both ways. Recursion uses the call stack, while iteration uses an explicit stack.
Q5: How is DFS applied in real life?
DFS is used in maze solving, social network analysis, dependency resolution, and AI pathfinding.
Conclusion
Depth-First Search is a foundational algorithm for traversing graphs and trees. The PHP examples—covering recursion, iteration, path detection, weighted graphs, and connected components—show how versatile and practical DFS can be. By practicing DFS, beginners strengthen their understanding of recursion, stacks, graph representation, and problem-solving strategies. Exploring DFS opens the door to more advanced graph algorithms like BFS, Dijkstra’s, and topological sorting.
