Breadth-First Search, or BFS, is a fundamental algorithm used to explore graphs and trees level by level. Unlike Depth-First Search, which dives as deep as possible along a branch, BFS explores all neighbors of a node first before moving to the next level. This makes it particularly useful for finding the shortest path in unweighted graphs, traversing networks, or analyzing hierarchical data structures.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, BFS is a great way to understand queues, graph traversal, and systematic exploration. It is widely used in real-world applications like social network analysis, web crawlers, shortest path calculations, and even solving puzzles or games. By learning BFS in JavaScript, you gain a solid foundation for handling graphs efficiently, which is an essential skill in both programming and algorithm design.
Program 1: BFS Using Queue on a Graph
This program demonstrates BFS using a queue on a predefined graph to explore nodes level by level.
const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: ['F'],
F: []
};
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
while (queue.length > 0) {
const node = queue.shift();
if (!visited.has(node)) {
console.log(node);
visited.add(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
}
}
}
}
}
bfs(graph, 'A');In this program, BFS uses a queue to keep track of nodes to visit. Beginners can understand it as “explore all neighbors first, then move to the next level.” It is useful for finding the shortest path or exploring all nodes systematically.
Program 2: BFS to Find Shortest Path
This example shows how BFS can be used to find the shortest path between two nodes in an unweighted graph.
const graphPath = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: ['F'],
F: []
};
function bfsShortestPath(graph, start, target) {
const visited = new Set();
const queue = [[start]];
while (queue.length > 0) {
const path = queue.shift();
const node = path[path.length - 1];
if (!visited.has(node)) {
if (node === target) return path;
visited.add(node);
for (let neighbor of graph[node]) {
const newPath = [...path, neighbor];
queue.push(newPath);
}
}
}
return null;
}
console.log("Shortest path from A to F:", bfsShortestPath(graphPath, 'A', 'F'));This program keeps track of paths while performing BFS to return the shortest path. Beginners can understand it as “check each level and remember the path to reach nodes.” It is especially useful for routing, navigation, or game development.
Program 3: BFS on a Tree Structure
This program applies BFS to traverse a tree represented as nested objects.
const tree = {
value: 'A',
children: [
{ value: 'B', children: [{ value: 'D', children: [] }, { value: 'E', children: [] }] },
{ value: 'C', children: [{ value: 'F', children: [] }] }
]
};
function bfsTree(root) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
console.log(node.value);
for (let child of node.children) {
queue.push(child);
}
}
}
bfsTree(tree);This BFS program explores nodes level by level in a tree. Beginners can visualize it as “look at each layer of the tree before going deeper.” It is useful for DOM traversal, organizational charts, or hierarchical data processing.
Program 4: BFS to Detect Connected Components
This example uses BFS to find all connected components in a graph.
const undirectedGraph = {
A: ['B'],
B: ['A', 'C'],
C: ['B'],
D: ['E'],
E: ['D'],
F: []
};
function bfsConnectedComponents(graph) {
const visited = new Set();
const components = [];
for (let node in graph) {
if (!visited.has(node)) {
const component = [];
const queue = [node];
while (queue.length > 0) {
const current = queue.shift();
if (!visited.has(current)) {
visited.add(current);
component.push(current);
for (let neighbor of graph[current]) {
if (!visited.has(neighbor)) queue.push(neighbor);
}
}
}
components.push(component);
}
}
return components;
}
console.log("Connected components:", bfsConnectedComponents(undirectedGraph));This program uses BFS to explore and group connected nodes. Beginners can think of it as “visit everything reachable from a node, then move to the next unvisited node.” It is useful for social network analysis, cluster detection, or graph segmentation.
Program 5: BFS for Level Order Traversal of a Binary Tree
This program demonstrates BFS to perform level-order traversal of a binary tree.
const binaryTree = {
value: 1,
left: { value: 2, left: { value: 4, left: null, right: null }, right: { value: 5, left: null, right: null } },
right: { value: 3, left: null, right: { value: 6, left: null, right: null } }
};
function bfsBinaryTree(root) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
console.log(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
bfsBinaryTree(binaryTree);This BFS program visits nodes level by level in a binary tree. Beginners can understand it as “explore all nodes in one row before moving to the next.” It is useful for printing trees, processing hierarchical data, or implementing algorithms that depend on node levels.
Frequently Asked Questions (FAQ)
This section addresses common beginner questions about BFS in JavaScript.
Q1. What is Breadth-First Search?
Breadth-First Search is an algorithm that explores nodes of a graph or tree level by level, visiting all neighbors before going deeper.
Q2. Can BFS handle cycles in graphs?
Yes, by keeping track of visited nodes, BFS can handle cycles safely.
Q3. How is BFS different from DFS?
BFS explores level by level, while DFS goes as deep as possible along a branch before backtracking.
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 in the graph.
Q5. When should I use BFS over DFS?
BFS is preferred when you need the shortest path in unweighted graphs or when exploring level-wise relationships.
Conclusion
Breadth-First Search is a versatile and widely used algorithm for graph and tree traversal.
By practicing BFS implementations on graphs, trees, level-order traversals, shortest path finding, and connected components, beginners can strengthen their understanding of systematic exploration. BFS also teaches important programming concepts like queues, sets, and iterative processing, providing a strong foundation for more advanced graph algorithms and real-world problem-solving in JavaScript.
