Breadth-First Search (BFS) and Depth-First Search (DFS) are two fundamental algorithms used in computer science and data analysis to traverse and search data structures like graphs and trees.
These algorithms can be applied to many problems, such as finding the shortest path between two points, checking for cycles in a graph, or searching for specific elements in a data structure.
In this article, we'll explore the basics of BFS and DFS algorithms, provide examples of their usage with different data structures, and explain how they work using JavaScript code.
By the end of this article, you'll have a strong understanding of both algorithms and be able to apply them to your own projects.
Overview
BFS is a graph traversal algorithm that visits all nodes in a graph or tree in level-order, meaning it visits all nodes at a given depth before moving on to the next depth. To implement BFS in JavaScript, we typically use a queue data structure to keep track of the nodes we need to visit next.
DFS is another graph traversal algorithm used to visit all the nodes in a graph or tree. Unlike BFS, DFS visits nodes in depth-first order, meaning it explores as far as possible along each branch before backtracking.
In JavaScript, we can implement DFS using a stack data structure to keep track of the nodes to visit next. This allows us to visit nodes in a depth-first order by first exploring the last visited node and its unvisited neighbors before moving on to the next node.
BFS & DFS Traversal for a Graph
Let's consider the following graph:
A -- B -- C
| |
D -- E -- F
To represent this graph in JavaScript, we can use an adjacency list:
const graph = {
A: ['B', 'D'],
B: ['A', 'C', 'E'],
C: ['B'],
D: ['A', 'E'],
E: ['B', 'D', 'F'],
F: ['E'],
};
Implementation of BFS using a queue to traverse the graph:
function bfs(graph, start) {
const queue = [start];
const visited = new Set();
const result = [];
while (queue.length) {
const vertex = queue.shift();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
for (const neighbor of graph[vertex]) {
queue.push(neighbor);
}
}
}
return result;
}
bfs(graph, 'A'); // ['A', 'B', 'D', 'C', 'E', 'F']
In this example, the BFS algorithm is implemented using a queue data structure, which holds the nodes that are to be processed in the order they were discovered.
The visited set is used to keep track of the nodes that have already been visited, and the result array stores the order in which the nodes were visited.
We start by adding the start node to the queue and processing it. Then, we add its neighbors to the queue and process them in the order they were added. We repeat this process until there are no more nodes to process.
Finally, we return the result array, which contains the nodes in the order they were visited by the BFS algorithm.
Implementation of DFS using a stack for the given graph:
function dfs(graph, start) {
const stack = [start];
const visited = new Set();
const result = [];
while (stack.length) {
const vertex = stack.pop();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
for (const neighbor of graph[vertex]) {
stack.push(neighbor);
}
}
}
return result;
}
dfs(graph, 'A'); // ['A', 'D', 'E', 'F', 'B', 'C']
In this example, the DFS algorithm is implemented using a stack data structure, which holds the nodes that are to be processed in the order they were discovered.
The visited set is used to keep track of the nodes that have already been visited, and the result array stores the order in which the nodes were visited. We start by adding the start node to the stack and processing it.
Then, we add its neighbors to the stack and process them in the order they were added. We repeat this process until there are no more nodes to process. If we encounter a node that has already been visited, we simply skip it and continue to the next node.
Finally, we return the result array, which contains the nodes in the order they were visited by the DFS algorithm.
BFS & DFS Traversal for a Tree
Let's consider the following tree:
1
/ \
2 3
/ \ / \
4 5 6 7
Example of this tree realization in JS:
function createNode(value, left = null, right = null) {
return { value, left, right };
}
const tree = createNode(1,
createNode(2,
createNode(4),
createNode(5)
),
createNode(3,
createNode(6),
createNode(7)
)
);
Implementation of BFS using a queue to traverse the graph:
function bfs(node) {
if (!node) {
return [];
}
const queue = [node];
const result = [];
while (queue.length) {
const current = queue.shift();
result.push(current.value);
if (current.left) {
queue.push(current.left);
}
if (current.right) {
queue.push(current.right);
}
}
return result;
}
bfs(tree); // [1, 2, 3, 4, 5, 6, 7]
This BFS solution implements a breadth-first traversal of a tree using a queue data structure. The algorithm starts by adding the root node to the queue and processing it. Then, it dequeues the first node from the queue and adds its value to the result array.
The algorithm then checks if the dequeued node has a left child and enqueues it onto the queue if it exists. Next, it checks if the dequeued node has a right child and enqueues it onto the queue if it exists. The algorithm repeats this process until there are no more nodes on the queue.
If the input node is null, an empty array is returned. The result array contains the values of the nodes in the order they were visited by the BFS algorithm.
Implementation of DFS using a stack to traverse the graph:
function dfs(node) {
if (!node) {
return [];
}
const stack = [node];
const result = [];
while (stack.length > 0) {
const current = stack.pop();
result.push(current.value);
if (current.right) {
stack.push(current.right);
}
if (current.left) {
stack.push(current.left);
}
}
return result;
}
dfs(tree); // [1, 2, 4, 5, 3, 6, 7]
This DFS solution implements a depth-first traversal of a tree using a stack data structure. The algorithm starts by adding the root node to the stack and processing it. Then, it pops the last node from the stack and adds its value to the result array.
The algorithm then checks if the popped node has a right child and pushes it onto the stack if it exists.
Next, it checks if the popped node has a left child and pushes it onto the stack if it exists. The algorithm repeats this process until there are no more nodes on the stack. If the input node is null, an empty array is returned.
The result array contains the values of the nodes in the order they were visited by the DFS algorithm.
Conclusion
In conclusion, both BFS and DFS are powerful algorithms that can be used to traverse a wide variety of data structures. BFS is an excellent choice for finding the shortest path between two points or for traversing a data structure level by level.
It is particularly effective when the data structure has many levels with few nodes. On the other hand, DFS is well-suited for searching for a particular node or for exploring a branch of a data structure in depth.
It is usually preferred when memory usage is a concern or when the data structure has many nodes with few levels.