Graphs are one of the most important data structures in programming, and searching through them efficiently is a skill every programmer should have. One of the most popular methods for exploring a graph is Depth-First Search (DFS). DFS starts at a chosen node and explores as far as possible along each branch before backtracking. This approach is excellent for tasks like solving mazes, checking connectivity in networks, or exploring decision trees.
with hands-on learning.
get the skills and confidence to land your next move.
Depth-First Search is beginner-friendly because it introduces the concept of recursion naturally. By visiting nodes and keeping track of the visited ones, DFS demonstrates how simple logic can be applied to complex structures. In F#, DFS can be implemented using recursion or with a stack, helping beginners understand both functional and imperative styles of programming.
Program 1: Recursive DFS on an Adjacency List
This program demonstrates a classic recursive DFS approach on a graph represented as an adjacency list.
open System
open System.Collections.Generic
let dfsRecursive (graph: Dictionary<int, List<int>>) start =
let visited = HashSet<int>()
let rec dfs node =
if visited.Add(node) then
printf "%d " node
for neighbor in graph.[node] do
dfs neighbor
dfs start
[<EntryPoint>]
let main argv =
let graph = Dictionary<int, List<int>>()
graph.Add(0, List<int>([1; 2]))
graph.Add(1, List<int>([0; 3; 4]))
graph.Add(2, List<int>([0; 4]))
graph.Add(3, List<int>([1; 5]))
graph.Add(4, List<int>([1; 2; 5]))
graph.Add(5, List<int>([3; 4]))
printf "DFS starting from node 0: "
dfsRecursive graph 0
printfn ""
0In this program, the dfsRecursive function uses a HashSet to keep track of visited nodes and prints each node as it is visited. Beginners can see how recursion naturally explores deeper nodes before backtracking, making it a clear demonstration of DFS principles.
Program 2: DFS Using a Stack
Sometimes, using recursion may not be ideal due to stack overflow in large graphs. This program demonstrates DFS using an explicit stack.
open System
open System.Collections.Generic
let dfsStack (graph: Dictionary<int, List<int>>) start =
let visited = HashSet<int>()
let stack = Stack<int>()
stack.Push(start)
while stack.Count > 0 do
let node = stack.Pop()
if visited.Add(node) then
printf "%d " node
// Convert .NET List<int> to F# list for iteration
for neighbor in List.ofSeq graph.[node] |> List.rev do
stack.Push(neighbor)
[<EntryPoint>]
let main argv =
let graph = Dictionary<int, List<int>>()
graph.Add(0, List<int>([1; 2]))
graph.Add(1, List<int>([0; 3; 4]))
graph.Add(2, List<int>([0; 4]))
graph.Add(3, List<int>([1; 5]))
graph.Add(4, List<int>([1; 2; 5]))
graph.Add(5, List<int>([3; 4]))
printf "DFS using stack starting from node 0: "
dfsStack graph 0
printfn ""
0Here, a stack replaces recursion. Nodes are pushed onto the stack and explored one by one. This method is practical for large graphs and helps beginners understand how DFS can be implemented iteratively.
Program 3: DFS on a 2D Grid
DFS is often used in grids, such as mazes or maps. This program demonstrates DFS traversal on a 2D array.
open System
let rows, cols = 3, 3
let directions = [ (0,1); (1,0); (0,-1); (-1,0) ]
let dfsGrid (grid:int[,]) (x:int) (y:int) (visited: bool[,]) =
let rec dfs i j =
if i >= 0 && i < rows && j >= 0 && j < cols && not visited.[i,j] then
visited.[i,j] <- true
printf "(%d,%d) " i j
for (di,dj) in directions do
dfs (i+di) (j+dj)
dfs x y
[<EntryPoint>]
let main argv =
let grid = array2D [ [1;1;0]; [0;1;1]; [1;0;1] ]
let visited = Array2D.create rows cols false
printf "DFS on grid starting at (0,0): "
dfsGrid grid 0 0 visited
printfn ""
0This example shows DFS applied to a 2D structure. The visited matrix ensures no cell is visited twice. Beginners can relate this to real-world problems like pathfinding in maps.
Program 4: DFS with Path Tracking
DFS can also track the path it takes. This program stores the nodes visited in order to reconstruct the path.
open System
open System.Collections.Generic
let dfsWithPath (graph: Dictionary<int, List<int>>) start =
let visited = HashSet<int>()
let path = ResizeArray<int>()
let rec dfs node =
if visited.Add(node) then
path.Add(node)
for neighbor in graph.[node] do
dfs neighbor
dfs start
path
[<EntryPoint>]
let main argv =
let graph = Dictionary<int, List<int>>()
graph.Add(0, List<int>([1; 2]))
graph.Add(1, List<int>([0; 3; 4]))
graph.Add(2, List<int>([0; 4]))
graph.Add(3, List<int>([1; 5]))
graph.Add(4, List<int>([1; 2; 5]))
graph.Add(5, List<int>([3; 4]))
let path = dfsWithPath graph 0
printf "DFS path from node 0: "
path |> Seq.iter (printf "%d ")
printfn ""
0This implementation is useful for problems where the exact order of traversal matters, such as generating mazes or solving puzzles. Beginners learn how to collect data while traversing a graph.
Program 5: DFS on a Graph with Cycles
Graphs may contain cycles, and DFS must handle them properly to avoid infinite loops. This program shows DFS on a cyclic graph.
open System
open System.Collections.Generic
let dfsCyclic (graph: Dictionary<int, List<int>>) start =
let visited = HashSet<int>()
let rec dfs node =
if visited.Add(node) then
printf "%d " node
for neighbor in graph.[node] do
dfs neighbor
dfs start
[<EntryPoint>]
let main argv =
let graph = Dictionary<int, List<int>>()
graph.Add(0, List<int>([1; 2]))
graph.Add(1, List<int>([0; 2]))
graph.Add(2, List<int>([0; 1; 3]))
graph.Add(3, List<int>([2]))
printf "DFS on cyclic graph starting from node 0: "
dfsCyclic graph 0
printfn ""
0By keeping track of visited nodes, DFS avoids revisiting nodes in cycles. This teaches beginners the importance of bookkeeping in graph algorithms.
Frequently Asked Questions (FAQ)
Q1. What is Depth-First Search?
DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
Q2. Does DFS work on both directed and undirected graphs?
Yes, DFS can be applied to both types, but the implementation may vary slightly.
Q3. How does DFS differ from BFS?
DFS goes deep into one branch before exploring others, while BFS explores neighbors level by level.
Q4. Can DFS detect cycles?
Yes, DFS can detect cycles by keeping track of visited nodes.
Q5. Is DFS suitable for large graphs?
DFS is efficient, but recursion may cause stack overflow in very large graphs, so iterative implementations with a stack are preferred.
Conclusion
Depth-First Search is a fundamental algorithm for exploring graphs, grids, and other connected structures. Through multiple F# programs, we saw recursive and iterative approaches, handling grids, tracking paths, and managing cycles.
For beginners, practicing DFS strengthens understanding of recursion, data structures, and algorithmic thinking. Exploring different graph types and scenarios prepares learners for more complex problems like shortest path finding, topological sorting, and network analysis.
