Breadth-First Search (BFS) is a fundamental algorithm for traversing graphs and trees, visiting nodes level by level. Unlike Depth-First Search, which goes deep along one branch before backtracking, BFS explores all neighbors of a node first before moving to the next level. This makes it ideal for finding the shortest path, exploring networks, and solving puzzles. For beginners, learning BFS helps build a strong foundation in graph algorithms and problem-solving strategies.
with hands-on learning.
get the skills and confidence to land your next move.
BFS is widely used in computer science, from social network analysis to game development and network routing. Its systematic approach ensures every reachable node is visited in a predictable order. Understanding BFS not only improves your programming skills but also prepares you to tackle real-world problems that involve structured data, maps, or connections.
Program 1: Basic BFS on a Graph
This program demonstrates a simple BFS traversal on a predefined graph represented using an adjacency list. It prints the nodes in the order they are visited.
Module Module1
Sub BFS(start As Integer, adj()() As Integer)
Dim n As Integer = adj.Length
Dim visited(n - 1) As Boolean
Dim queue As New Queue(Of Integer)
visited(start) = True
queue.Enqueue(start)
While queue.Count > 0
Dim node As Integer = queue.Dequeue()
Console.Write(node & " ")
For Each neighbor In adj(node)
If Not visited(neighbor) Then
visited(neighbor) = True
queue.Enqueue(neighbor)
End If
Next
End While
End Sub
Sub Main()
Dim n As Integer = 5
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1, 2}
adj(1) = New Integer() {0, 3, 4}
adj(2) = New Integer() {0}
adj(3) = New Integer() {1}
adj(4) = New Integer() {1}
Console.WriteLine("BFS starting from node 0:")
BFS(0, adj)
Console.ReadLine()
End Sub
End ModuleThe BFS uses a queue to manage the nodes to visit. Nodes are marked as visited to avoid revisiting. Beginners can see how BFS systematically explores all neighbors, providing a clear level-by-level traversal.
Program 2: BFS for Finding Shortest Path in an Unweighted Graph
This program uses BFS to calculate the shortest distance from a starting node to all other nodes in an unweighted graph.
Module Module1
Sub BFSShortestPath(start As Integer, adj()() As Integer)
Dim n As Integer = adj.Length
Dim visited(n - 1) As Boolean
Dim distance(n - 1) As Integer
For i As Integer = 0 To n - 1
distance(i) = -1
Next
Dim queue As New Queue(Of Integer)
visited(start) = True
distance(start) = 0
queue.Enqueue(start)
While queue.Count > 0
Dim node As Integer = queue.Dequeue()
For Each neighbor In adj(node)
If Not visited(neighbor) Then
visited(neighbor) = True
distance(neighbor) = distance(node) + 1
queue.Enqueue(neighbor)
End If
Next
End While
Console.WriteLine("Shortest distances from node " & start & ":")
For i As Integer = 0 To n - 1
Console.WriteLine("Node " & i & ": " & distance(i))
Next
End Sub
Sub Main()
Dim n As Integer = 5
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1, 2}
adj(1) = New Integer() {0, 3, 4}
adj(2) = New Integer() {0}
adj(3) = New Integer() {1}
adj(4) = New Integer() {1}
BFSShortestPath(0, adj)
Console.ReadLine()
End Sub
End ModuleBFS naturally calculates the shortest path in unweighted graphs because it visits nodes level by level. The distance array keeps track of the distance from the starting node. Beginners can understand that BFS is powerful not just for traversal but also for finding optimal paths.
Program 3: BFS on a Grid (Maze Traversal)
This program demonstrates BFS applied to a 2D grid, which is common in games or pathfinding applications.
Module Module1
Dim rows As Integer = 4
Dim cols As Integer = 4
Dim grid(,) As Integer = {
{0, 1, 0, 0},
{0, 1, 0, 1},
{0, 0, 0, 1},
{1, 1, 0, 0}
}
Dim visited(3, 3) As Boolean
Sub BFS(x As Integer, y As Integer)
Dim queue As New Queue(Of Tuple(Of Integer, Integer))
queue.Enqueue(Tuple.Create(x, y))
visited(x, y) = True
Dim directions()() As Integer = {
New Integer() {1, 0},
New Integer() {-1, 0},
New Integer() {0, 1},
New Integer() {0, -1}
}
While queue.Count > 0
Dim current As Tuple(Of Integer, Integer) = queue.Dequeue()
Console.Write("(" & current.Item1 & "," & current.Item2 & ") ")
For Each dir As Integer() In directions
Dim newX As Integer = current.Item1 + dir(0)
Dim newY As Integer = current.Item2 + dir(1)
' First check bounds
If newX >= 0 And newX < rows And newY >= 0 And newY < cols Then
' Only now check grid and visited
If grid(newX, newY) = 0 And Not visited(newX, newY) Then
visited(newX, newY) = True
queue.Enqueue(Tuple.Create(newX, newY))
End If
End If
Next
End While
End Sub
Sub Main()
Console.WriteLine("BFS traversal of grid starting at (0,0):")
BFS(0, 0)
Console.ReadLine()
End Sub
End ModuleBFS explores all reachable cells from a starting point, making it ideal for maze solving and shortest path in grids. Beginners can see BFS applied beyond abstract graphs to practical, real-world structures.
Program 4: BFS for Connected Components in a Graph
This program counts the number of connected components in a graph using BFS.
Module Module1
Sub BFS(node As Integer, adj()() As Integer, visited() As Boolean)
Dim queue As New Queue(Of Integer)
visited(node) = True
queue.Enqueue(node)
While queue.Count > 0
Dim current As Integer = queue.Dequeue()
For Each neighbor In adj(current)
If Not visited(neighbor) Then
visited(neighbor) = True
queue.Enqueue(neighbor)
End If
Next
End While
End Sub
Sub Main()
Dim n As Integer = 6
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1}
adj(1) = New Integer() {0}
adj(2) = New Integer() {3}
adj(3) = New Integer() {2}
adj(4) = New Integer() {}
adj(5) = New Integer() {}
Dim visited(n - 1) As Boolean
Dim count As Integer = 0
For i As Integer = 0 To n - 1
If Not visited(i) Then
BFS(i, adj, visited)
count += 1
End If
Next
Console.WriteLine("Number of connected components: " & count)
Console.ReadLine()
End Sub
End ModuleEach BFS traversal covers a connected component. Calling BFS on unvisited nodes ensures all disconnected components are counted. Beginners can see BFS applied to real network analysis.
Program 5: BFS for Level Order Traversal in a Binary Tree
This program demonstrates BFS in the context of a binary tree, known as level-order traversal.
Module Module1
Class Node
Public data As Integer
Public left As Node
Public right As Node
Sub New(val As Integer)
data = val
left = Nothing
right = Nothing
End Sub
End Class
Sub LevelOrder(root As Node)
If root Is Nothing Then Return
Dim queue As New Queue(Of Node)
queue.Enqueue(root)
While queue.Count > 0
Dim node As Node = queue.Dequeue()
Console.Write(node.data & " ")
If node.left IsNot Nothing Then queue.Enqueue(node.left)
If node.right IsNot Nothing Then queue.Enqueue(node.right)
End While
End Sub
Sub Main()
Dim root As New Node(1)
root.left = New Node(2)
root.right = New Node(3)
root.left.left = New Node(4)
root.left.right = New Node(5)
Console.WriteLine("Level-order traversal of the tree:")
LevelOrder(root)
Console.ReadLine()
End Sub
End ModuleBFS naturally traverses trees level by level, making it easy to understand hierarchical structures. Beginners can relate BFS to real-world problems like organizational charts or family trees.
Frequently Asked Questions (FAQ)
Here are some common questions beginners ask about Breadth-First Search:
Q1: What is BFS used for?
BFS is used for graph traversal, shortest path finding in unweighted graphs, level-order tree traversal, and network analysis.
Q2: Can BFS be implemented recursively?
BFS is typically implemented iteratively using a queue, but recursive versions using auxiliary structures exist.
Q3: How is BFS different from DFS?
BFS visits nodes level by level, while DFS goes deep into one branch before backtracking.
Q4: Can BFS handle disconnected graphs?
Yes, by calling BFS on unvisited nodes, you can cover all components.
Q5: Is BFS useful for grids and mazes?
Absolutely, BFS is ideal for shortest path problems and exploration in 2D grids.
Conclusion
Breadth-First Search is a versatile and essential algorithm for exploring graphs, trees, and grids. From basic traversal to shortest path calculation, grid exploration, and connected component analysis, BFS has countless applications in computer science and programming. Practicing BFS in VB .NET helps beginners visualize algorithmic thinking, solve complex problems, and build strong foundations for advanced algorithms.
