Graphs are everywhere in computer science, from social networks and web pages to maps and network routing. To work effectively with graphs, it’s crucial to understand graph traversal techniques. One of the most important algorithms for traversing graphs is Breadth-First Search (BFS). Unlike Depth-First Search, BFS explores a graph level by level, starting from a source node and visiting all its neighbors before moving on to the next level. This property makes BFS ideal for finding shortest paths in unweighted graphs, analyzing social connections, and exploring tree-like structures.
with hands-on learning.
get the skills and confidence to land your next move.
BFS is widely used in pathfinding algorithms, network broadcasting, and solving puzzles like the shortest route in a maze. By learning BFS, beginners gain a strong foundation in queues, graph traversal, and algorithmic thinking. Understanding BFS also paves the way for advanced topics like Dijkstra’s Algorithm, Ford-Fulkerson for flow networks, and AI search techniques.
Program 1: BFS Using Queue on an Adjacency Matrix
This program demonstrates the basic BFS approach using a queue and an adjacency matrix. It explores all nodes of the graph starting from a specified node.
using System;
using System.Collections.Generic;
class Program
{
static void BFS(int[,] graph, int start)
{
int n = graph.GetLength(0);
bool[] visited = new bool[n];
Queue<int> queue = new Queue<int>();
visited[start] = true;
queue.Enqueue(start);
while (queue.Count > 0)
{
int node = queue.Dequeue();
Console.Write(node + " ");
for (int i = 0; i < n; i++)
{
if (graph[node, i] == 1 && !visited[i])
{
visited[i] = true;
queue.Enqueue(i);
}
}
}
}
static void Main()
{
int[,] graph = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 1, 0}
};
Console.WriteLine("BFS starting from node 0:");
BFS(graph, 0);
}
}In this program, BFS starts at the chosen node, marks it as visited, and enqueues all unvisited neighbors. By processing nodes in a queue, it ensures that nodes are explored level by level. Beginners can use this approach to understand how BFS systematically visits every node in the shortest path order.
Program 2: BFS Using Adjacency List
Graphs are often represented as adjacency lists, which save memory for sparse graphs. This example shows BFS using a dictionary of lists.
using System;
using System.Collections.Generic;
class Program
{
static void BFSList(Dictionary<int, List<int>> graph, int start)
{
HashSet<int> visited = new HashSet<int>();
Queue<int> queue = new Queue<int>();
visited.Add(start);
queue.Enqueue(start);
while (queue.Count > 0)
{
int node = queue.Dequeue();
Console.Write(node + " ");
foreach (var neighbor in graph[node])
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
}
static void Main()
{
var graph = new Dictionary<int, List<int>>()
{
{0, new List<int>{1,2}},
{1, new List<int>{0,3,4}},
{2, new List<int>{0}},
{3, new List<int>{1,4}},
{4, new List<int>{1,3}}
};
Console.WriteLine("BFS on adjacency list starting from node 0:");
BFSList(graph, 0);
}
}This program works by enqueuing neighbors of each node and marking them visited. Using an adjacency list makes BFS memory-efficient for large graphs. Beginners can easily understand how the queue guarantees that nodes are processed in the order they are discovered.
Program 3: BFS to Find Shortest Path in an Unweighted Graph
BFS can also find the shortest path from a source node to other nodes in an unweighted graph. This program demonstrates that functionality.
using System;
using System.Collections.Generic;
class Program
{
static void BFSShortestPath(Dictionary<int, List<int>> graph, int start)
{
Dictionary<int, int> distance = new Dictionary<int, int>();
Queue<int> queue = new Queue<int>();
foreach (var node in graph.Keys)
{
distance[node] = int.MaxValue;
}
distance[start] = 0;
queue.Enqueue(start);
while (queue.Count > 0)
{
int node = queue.Dequeue();
foreach (var neighbor in graph[node])
{
if (distance[neighbor] == int.MaxValue)
{
distance[neighbor] = distance[node] + 1;
queue.Enqueue(neighbor);
}
}
}
foreach (var kvp in distance)
{
Console.WriteLine($"Distance from node {start} to node {kvp.Key}: {kvp.Value}");
}
}
static void Main()
{
var graph = new Dictionary<int, List<int>>()
{
{0, new List<int>{1,2}},
{1, new List<int>{0,3,4}},
{2, new List<int>{0}},
{3, new List<int>{1,4}},
{4, new List<int>{1,3}}
};
Console.WriteLine("Shortest paths from node 0:");
BFSShortestPath(graph, 0);
}
}This BFS version tracks distances from the start node, allowing it to find the shortest path in an unweighted graph. Beginners can see how BFS naturally discovers nodes in increasing order of distance.
Program 4: BFS to Detect Connected Components
BFS is useful not only for traversal but also for graph analysis, such as counting connected components in an undirected graph.
using System;
using System.Collections.Generic;
class Program
{
static void BFSComponent(Dictionary<int, List<int>> graph, int start, HashSet<int> visited)
{
Queue<int> queue = new Queue<int>();
visited.Add(start);
queue.Enqueue(start);
while (queue.Count > 0)
{
int node = queue.Dequeue();
foreach (var neighbor in graph[node])
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
}
static void Main()
{
var graph = new Dictionary<int, List<int>>()
{
{0, new List<int>{1}},
{1, new List<int>{0}},
{2, new List<int>{3}},
{3, new List<int>{2}},
{4, new List<int>()}
};
HashSet<int> visited = new HashSet<int>();
int components = 0;
foreach (var node in graph.Keys)
{
if (!visited.Contains(node))
{
BFSComponent(graph, node, visited);
components++;
}
}
Console.WriteLine($"Number of connected components: {components}");
}
}Here, BFS visits all nodes in each component before moving to the next. Beginners can understand how BFS helps in analyzing graph structure, not just traversing nodes.
Frequently Asked Questions (FAQ)
Q1: What is Breadth-First Search used for?
BFS is used to traverse graphs level by level, find shortest paths in unweighted graphs, and detect connected components.
Q2: What is the difference between BFS and DFS?
BFS explores nodes level by level, while DFS goes deep into a branch before backtracking.
Q3: Can BFS be implemented recursively?
BFS is usually implemented iteratively using a queue. Recursive BFS is possible but less common and often inefficient.
Q4: What is the time complexity of BFS?
The time complexity is O(V + E), where V is the number of vertices and E is the number of edges.
Q5: Is BFS suitable for weighted graphs?
BFS works for unweighted graphs. For weighted graphs, algorithms like Dijkstra’s are required to find shortest paths.
Conclusion
Breadth-First Search is an essential algorithm for graph traversal and analysis. By learning BFS with queues, adjacency matrices, adjacency lists, and practical applications like shortest paths and connected components, beginners gain a solid foundation in graph algorithms. Practicing BFS helps programmers understand how to systematically explore graphs, which is critical in many real-world applications, from network routing to puzzle solving and AI pathfinding. Experimenting with BFS on different graphs strengthens your problem-solving skills and prepares you for advanced graph algorithms in C#.
