Graphs are everywhere in programming, from social networks to maps and computer networks. Searching through these graphs efficiently is a key skill for any programmer, and Breadth-First Search (BFS) is one of the most important algorithms for this purpose. Unlike Depth-First Search, BFS explores a graph level by level, visiting all neighbors of a node before moving deeper. This makes BFS particularly useful for finding the shortest path in unweighted graphs, solving puzzles, and exploring networks.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, BFS is a friendly way to learn how queues and iterative logic work together. F# provides simple tools like lists, queues, and recursion to implement BFS, making it an excellent language for understanding the core ideas. By the end of this article, you will be able to write BFS programs that traverse graphs, handle grids, and even track paths efficiently.
Program 1: BFS Using a Queue on an Adjacency List
This program demonstrates the classic BFS approach on a graph represented with an adjacency list.
open System
open System.Collections.Generic
let bfsQueue (graph: Dictionary<int, List<int>>) start =
let visited = HashSet<int>()
let queue = Queue<int>()
queue.Enqueue(start)
visited.Add(start) |> ignore
while queue.Count > 0 do
let node = queue.Dequeue()
printf "%d " node
for neighbor in graph.[node] do
if visited.Add(neighbor) then
queue.Enqueue(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 "BFS starting from node 0: "
bfsQueue graph 0
printfn ""
0This program uses a Queue to process nodes in a FIFO order. By adding neighbors to the queue only if they haven’t been visited, BFS ensures all nodes are visited level by level. Beginners can easily see how a queue manages the order of exploration compared to a stack in DFS.
Program 2: BFS Tracking Paths
Sometimes, you want to know not just the nodes visited, but also the path taken to reach them. This program tracks BFS paths.
open System
open System.Collections.Generic
let bfsPath (graph: Dictionary<int, List<int>>) start =
let visited = HashSet<int>()
let queue = Queue<int>()
let parent = Dictionary<int, int>()
queue.Enqueue(start)
visited.Add(start) |> ignore
parent.[start] <- -1
while queue.Count > 0 do
let node = queue.Dequeue()
printf "%d " node
for neighbor in graph.[node] do
if visited.Add(neighbor) then
queue.Enqueue(neighbor)
parent.[neighbor] <- node
parent
[<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 parents = bfsPath graph 0
printfn "\nParent relationships:"
for kvp in parents do
printfn "Node %d came from %d" kvp.Key kvp.Value
0Here, the parent dictionary keeps track of which node led to the current one. This is useful in finding the shortest path from the start node to any other node. Beginners can see how BFS naturally provides a way to reconstruct paths.
Program 3: BFS on a 2D Grid
BFS is widely used for pathfinding in grids or maps. This program shows BFS on a 2D array.
open System
open System.Collections.Generic
let rows, cols = 3, 3
let directions = [ (0,1); (1,0); (0,-1); (-1,0) ]
let bfsGrid (grid:int[,]) startX startY =
let visited = Array2D.create rows cols false
let queue = Queue<int * int>()
queue.Enqueue(startX, startY)
visited.[startX, startY] <- true
while queue.Count > 0 do
let (x, y) = queue.Dequeue()
printf "(%d,%d) " x y
for (dx, dy) in directions do
let nx, ny = x + dx, y + dy
if nx >= 0 && nx < rows && ny >= 0 && ny < cols && not visited.[nx, ny] then
queue.Enqueue(nx, ny)
visited.[nx, ny] <- true
[<EntryPoint>]
let main argv =
let grid = array2D [ [1;1;0]; [0;1;1]; [1;0;1] ]
printf "BFS on grid starting at (0,0): "
bfsGrid grid 0 0
printfn ""
0This example highlights BFS for map traversal. The visited array prevents revisiting cells, while the queue ensures nodes are processed level by level. Beginners can relate this to pathfinding in games or real-world maps.
Program 4: BFS on a Cyclic Graph
Graphs often contain cycles, and BFS handles them naturally with a visited set.
open System
open System.Collections.Generic
let bfsCyclic (graph: Dictionary<int, List<int>>) start =
let visited = HashSet<int>()
let queue = Queue<int>()
queue.Enqueue(start)
visited.Add(start) |> ignore
while queue.Count > 0 do
let node = queue.Dequeue()
printf "%d " node
for neighbor in graph.[node] do
if visited.Add(neighbor) then
queue.Enqueue(neighbor)
[<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 "BFS on cyclic graph starting from node 0: "
bfsCyclic graph 0
printfn ""
0Using a visited set prevents infinite loops even in cyclic graphs. Beginners can see the importance of bookkeeping in algorithms that explore connected structures.
Program 5: BFS for Shortest Path Length
BFS can also compute the minimum number of steps between two nodes in an unweighted graph.
open System
open System.Collections.Generic
let bfsShortestPath (graph: Dictionary<int, List<int>>) start target =
let visited = HashSet<int>()
let queue = Queue<int * int>() // node, distance
queue.Enqueue((start, 0))
visited.Add(start) |> ignore
let mutable found = false
while queue.Count > 0 && not found do
let (node, dist) = queue.Dequeue()
if node = target then
printfn "Shortest path from %d to %d is %d" start target dist
found <- true
else
for neighbor in graph.[node] do
if visited.Add(neighbor) then
queue.Enqueue((neighbor, dist + 1))
[<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]))
bfsShortestPath graph 0 5
0By storing distances alongside nodes, BFS computes the shortest path efficiently. Beginners can see BFS’s practical advantage for unweighted graphs and shortest-path problems.
Frequently Asked Questions (FAQ)
Q1. What is Breadth-First Search?
BFS is a graph traversal algorithm that visits all neighbors of a node before moving deeper into the graph.
Q2. Can BFS find the shortest path?
Yes, BFS finds the shortest path in unweighted graphs because it explores nodes level by level.
Q3. How does BFS differ from DFS?
DFS goes deep along one branch before backtracking, while BFS explores all neighbors before going deeper.
Q4. Does BFS work on cyclic graphs?
Yes, as long as you track visited nodes, BFS can handle cycles without looping infinitely.
Q5. Is BFS iterative or recursive?
BFS is usually implemented iteratively using a queue, but recursive variations are possible with more complex logic.
Conclusion
Breadth-First Search is a foundational algorithm for graph traversal, pathfinding, and network analysis. Through F# programs, we explored BFS with queues, grids, cyclic graphs, path tracking, and shortest path computation.
For beginners, practicing BFS develops understanding of queues, iterative logic, and graph structures. Once comfortable, BFS can be applied to real-world problems like maze solving, social network analysis, and routing in networks.
