When we start learning about graph algorithms, one of the first and most essential techniques we come across is Breadth-First Search (BFS). This algorithm explores nodes in a graph level by level, meaning it visits all nodes at the current depth before moving on to the next level. It’s the complete opposite of Depth-First Search, which dives deep into one branch before backtracking. BFS gives us a systematic and predictable way to explore all possible nodes step by step.
with hands-on learning.
get the skills and confidence to land your next move.
Breadth-First Search is widely used in computer science for solving real-world problems such as finding the shortest path in unweighted graphs, web crawling, peer-to-peer network exploration, and even social networking applications. For instance, if you want to find the shortest connection between two people on a social media platform, BFS is the perfect algorithm to use. In this article, we’ll walk through multiple Dart programs that implement BFS in different ways, including iterative, recursive, and user-input approaches. Each version will help you understand how BFS works under various conditions.
Program 1: Simple BFS Implementation Using Queue
This first program shows the most basic and commonly used approach to implementing Breadth-First Search using a queue. It provides the foundation for understanding BFS.
import 'dart:collection';
void bfs(Map<int, List<int>> graph, int start) {
Queue<int> queue = Queue<int>();
Set<int> visited = {};
queue.add(start);
visited.add(start);
while (queue.isNotEmpty) {
int node = queue.removeFirst();
print(node);
for (var neighbor in graph[node]!) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
void main() {
Map<int, List<int>> graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [],
5: []
};
print("Breadth-First Search starting from node 0:");
bfs(graph, 0);
}In this version, the BFS algorithm uses a queue to keep track of nodes to visit next. The algorithm begins at the starting node, marks it as visited, and explores its neighbors one by one. The use of a queue ensures that nodes are visited in a level-order manner. This method is simple, effective, and perfect for beginners who are learning how BFS systematically explores every connected node before moving to the next level.
Program 2: BFS with Adjacency Matrix Representation
While most graphs are represented as adjacency lists, we can also use an adjacency matrix to store edges. This approach is ideal for dense graphs where many nodes are connected.
import 'dart:collection';
void bfsMatrix(List<List<int>> graph, int start) {
Queue<int> queue = Queue<int>();
List<bool> visited = List.filled(graph.length, false);
queue.add(start);
visited[start] = true;
while (queue.isNotEmpty) {
int node = queue.removeFirst();
print(node);
for (int i = 0; i < graph.length; i++) {
if (graph[node][i] == 1 && !visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
void main() {
List<List<int>> graph = [
[0, 1, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 1, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 0, 1, 1, 0]
];
print("BFS traversal using adjacency matrix starting from node 0:");
bfsMatrix(graph, 0);
}This code represents a graph using a two-dimensional list. Each element graph[i][j] indicates whether there is a connection between node i and node j. The BFS algorithm checks all possible neighbors and visits each unvisited connected node. Beginners will find this version useful when working with dense networks or systems where connections between nodes are frequent and direct.
Program 3: BFS Using Recursion (Conceptual Simulation)
Though BFS is usually implemented iteratively, we can mimic its behavior using recursion by processing one level at a time.
void bfsRecursive(Map<int, List<int>> graph, List<int> currentLevel, Set<int> visited) {
if (currentLevel.isEmpty) return;
List<int> nextLevel = [];
for (int node in currentLevel) {
print(node);
for (var neighbor in graph[node]!) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
nextLevel.add(neighbor);
}
}
}
bfsRecursive(graph, nextLevel, visited);
}
void main() {
Map<int, List<int>> graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [],
5: []
};
print("BFS traversal using recursion starting from node 0:");
bfsRecursive(graph, [0], {0});
}Here, we use recursion to simulate BFS by keeping track of the current level of nodes and preparing the next level for recursive calls. Although recursion is not the typical way to write BFS, it helps beginners understand how level-based exploration works. It’s a great conceptual exercise to see how recursion can simulate queue-like behavior.
Program 4: BFS to Find the Shortest Path in an Unweighted Graph
Breadth-First Search can also be used to find the shortest path between two nodes in an unweighted graph. This is one of its most practical applications.
import 'dart:collection';
void shortestPath(Map<int, List<int>> graph, int start, int target) {
Queue<int> queue = Queue<int>();
Map<int, int> parent = {};
Set<int> visited = {};
queue.add(start);
visited.add(start);
parent[start] = -1;
while (queue.isNotEmpty) {
int node = queue.removeFirst();
if (node == target) break;
for (var neighbor in graph[node]!) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
parent[neighbor] = node;
queue.add(neighbor);
}
}
}
List<int> path = [];
int? current = target;
while (current != -1) {
path.insert(0, current!);
current = parent[current];
}
print("Shortest path from $start to $target: $path");
}
void main() {
Map<int, List<int>> graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [5],
5: []
};
shortestPath(graph, 0, 5);
}In this version, BFS not only visits all nodes but also tracks their parents to reconstruct the shortest path from the starting node to the target node. This method is useful in real-world scenarios such as routing and navigation systems, where you want to determine the quickest way to reach a destination.
Program 5: Interactive BFS with User Input
This program lets users create their own graphs and test BFS dynamically. It’s an engaging way for beginners to experiment with different graph structures.
import 'dart:collection';
import 'dart:io';
void bfsUserInput(Map<int, List<int>> graph, int start) {
Queue<int> queue = Queue<int>();
Set<int> visited = {};
queue.add(start);
visited.add(start);
while (queue.isNotEmpty) {
int node = queue.removeFirst();
print(node);
for (var neighbor in graph[node]!) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
void main() {
Map<int, List<int>> graph = {};
print("Enter the number of edges: ");
int edges = int.parse(stdin.readLineSync()!);
for (int i = 0; i < edges; i++) {
print("Enter edge (u v): ");
var input = stdin.readLineSync()!.split(" ");
int u = int.parse(input[0]);
int v = int.parse(input[1]);
graph.putIfAbsent(u, () => []);
graph.putIfAbsent(v, () => []);
graph[u]!.add(v);
}
print("Enter the starting node: ");
int start = int.parse(stdin.readLineSync()!);
print("BFS traversal starting from node $start:");
bfsUserInput(graph, start);
}This version accepts user input for graph creation and the starting node. It helps learners visualize BFS in action with custom examples. It’s a fantastic way to understand how the algorithm adapts to different graphs and real-time data input.
Frequently Asked Questions (FAQ)
Here are some common questions students often ask while learning Breadth-First Search in Dart.
Q1: What is Breadth-First Search (BFS)?
Breadth-First Search is a graph traversal algorithm that visits all nodes level by level before moving deeper into the structure.
Q2: Where is BFS used?
BFS is used in shortest path finding, social networks, peer-to-peer systems, and web crawlers.
Q3: What data structure is used in BFS?
A queue is used in BFS to keep track of the order of node visits.
Q4: How is BFS different from DFS?
BFS explores level by level, while DFS goes deep into one branch before backtracking.
Q5: Can BFS work on both directed and undirected graphs?
Yes, BFS works on both types of graphs with slight adjustments in how edges are handled.
Conclusion
Breadth-First Search is one of the most important and beginner-friendly algorithms in graph theory. Its level-wise traversal makes it easy to visualize and understand how data is connected and explored. In this article, we explored various Dart programs demonstrating BFS through iterative, recursive, and user-input methods, as well as practical uses like finding the shortest path.
For beginners, mastering BFS opens the door to understanding many other algorithms such as Dijkstra’s and A*. The best way to learn is through practice—modify these programs, try different graphs, and experiment with both directed and undirected versions. With time and practice, you’ll find BFS to be a simple yet powerful tool in your programming journey.
