Implementing Depth-First Search (DFS) and Breadth-First Search (BFS) on a Graph

Dive deeper into DFS and BFS algorithms, implement them in your code, and conquer graph-related challenges. Enhance your problem-solving abilities today!

Graph traversal algorithms play a crucial role in solving many graph-related problems. Two commonly used algorithms for graph traversal are Depth-First Search (DFS) and Breadth-First Search (BFS). In this article, we will explore how to implement DFS and BFS on a graph using JavaScript and compare their characteristics and use cases.

Photo by Chang Duong on Unsplash

Understanding Graphs

Before diving into the implementation, let’s understand the basic concepts of graphs. A graph is a collection of nodes (vertices) that are connected by edges. Graphs can be represented using various data structures, such as an adjacency matrix or adjacency list. In this article, we will use the adjacency list representation.

Depth-First Search (DFS)

DFS is an algorithm that explores a graph by visiting as far as possible along each branch before backtracking. It follows the principle of depth-first traversal, where it explores the depth of each branch before moving on to the next branch. DFS can be implemented using recursion or a stack.

Here’s an example implementation of DFS using recursion:

function dfs(graph, startNode, visited = new Set()) {
  visited.add(startNode);
  console.log(startNode);
  for (let neighbor of graph[startNode]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

Code Walkthro:

The dfs function takes three parameters: graph, startNode, and an optional visited set.

• graph represents the graph data structure, typically implemented as an adjacency list where each node is associated with an array of its neighboring nodes.
• startNode specifies the node from which the DFS traversal begins.
• visited is an optional set that keeps track of the visited nodes during the traversal.

The function starts by adding the startNode to the visited set using the add method. This ensures that the node is marked as visited and prevents revisiting it later.

Next, the startNode is printed to the console using console.log, indicating that it has been visited.

The function then enters a loop that iterates over each neighbor of the startNode obtained from the graph[startNode] array.

For each neighbor, it checks if it has already been visited by calling the has method on the visited set. If the neighbor has not been visited, the function recursively calls itself with the neighbor as the new startNode and the updated visited set.

This recursive call effectively performs a depth-first traversal by exploring the depth of each branch before backtracking to unexplored nodes.

By recursively visiting each neighbor, the function traverses the entire graph, ensuring that all reachable nodes are visited exactly once.

Overall, this code snippet demonstrates a basic implementation of the DFS algorithm, which is useful for various graph-related tasks, such as finding paths, cycles, or connected components in a graph.

Breadth-First Search (BFS)

BFS is an algorithm that explores a graph by visiting all its neighboring nodes before moving on to their respective neighbors. It follows the principle of breadth-first traversal, where it explores all the nodes at the same level before moving to the next level. BFS can be implemented using a queue.

Here’s an example implementation of BFS using a queue:

function bfs(graph, startNode) {
  const visited = new Set();
  const queue = [startNode];
  visited.add(startNode);
  while (queue.length > 0) {
    const currentNode = queue.shift();
    console.log(currentNode);
    for (let neighbor of graph[currentNode]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

Code Walkthro

The bfs function takes two parameters: graph and startNode.

• graph represents the graph data structure, typically implemented as an adjacency list where each node is associated with an array of its neighboring nodes.
• startNode specifies the node from which the BFS traversal begins.

The function initializes a visited set using the new Set() constructor to keep track of the visited nodes during the traversal.

A queue array is created and initialized with the startNode. The queue represents the nodes that are waiting to be visited.

The startNode is added to the visited set using the add method to mark it as visited.

The function enters a while loop that continues as long as there are nodes in the queue. This loop ensures that all nodes at each level are visited before moving on to the next level.

Within the loop, the first node (currentNode) is dequeued from the front of the queue using the shift method.

The currentNode is then printed to the console using console.log, indicating that it has been visited.

Next, the function iterates over each neighbor of the currentNode obtained from the graph[currentNode] array.

For each neighbor, it checks if it has already been visited by calling the has method on the visited set. If the neighbor has not been visited, it is added to the visited set using the add method, marking it as visited.

The neighbor is also enqueued to the queue array using the push method. This ensures that the neighbor will be visited in the subsequent iterations, after visiting all the nodes at the current level.

By dequeuing nodes from the queue and enqueuing their unvisited neighbors, the function explores the graph layer by layer, following a breadth-first approach.

Overall, this code snippet demonstrates a basic implementation of the BFS algorithm, which is commonly used for tasks such as finding the shortest path, performing level-order traversal, or exploring the graph layer by layer.

Comparing DFS and BFS

While DFS and BFS are both graph traversal algorithms, they have different characteristics and use cases.

• DFS explores the depth of a graph before backtracking. It follows a “depth-first” approach, which means it visits nodes as far as possible before backtracking to unexplored nodes. DFS is useful for finding paths, cycles, or connected components in a graph. It is implemented using recursion or a stack. DFS may not necessarily find the shortest path between two nodes.
• BFS explores all the neighboring nodes at the same level before moving to the next level. It follows a “breadth-first” approach, which means it visits nodes layer by layer. BFS is commonly used to find the shortest path, perform level-order traversal, or explore the graph layer by layer. It is implemented using a queue. BFS guarantees finding the shortest path between two nodes in an unweighted graph.

Putting it Together

To demonstrate the usage of DFS and BFS, let’s consider an example graph and perform both traversals on it.

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};
console.log("DFS:");
dfs(graph, "A");
console.log("BFS:");
bfs(graph, "A");

In the above code snippet, we create a graph using an adjacency list representation. We then call the dfs and bfs functions with the graph and the starting node "A". The traversal results are displayed in the console.

By running the code, you will observe the differences between DFS and BFS in terms of traversal order and the nodes they visit.

Summary

Depth-First Search (DFS) and Breadth-First Search (BFS) are fundamental graph traversal algorithms that enable us to explore and analyze graphs effectively. While DFS explores the depth of a graph before backtracking, BFS explores the graph layer by layer. Understanding their characteristics and use cases can help us choose the appropriate algorithm for solving different graph-related problems.

In this article, we implemented DFS and BFS in JavaScript and compared their key features. We also provided a practical example to demonstrate their usage. By applying these algorithms to your graph-related problems, you can gain insights and find optimal solutions.

Remember that both DFS and BFS have their strengths and limitations, and choosing the right algorithm depends on the specific problem and requirements. Being familiar with these traversal algorithms equips you with essential tools for graph analysis and problem-solving in the realm of computer science.

Hope the above article gave a better understanding. If you have any questions regarding the areas I have discussed in this article, areas of improvement don’t hesitate to comment below.

[Disclosure: This article is a collaborative creation blending my own ideation with the assistance of ChatGPT for optimal articulation.]