Depth First Search Algorithm (DFS)

The algorithm is used to traverse a graph and visit each of its vertices. The DFS algorithm starts at a root vertex, explores as far as possible along each branch before backtracking.

class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjList.has(vertex)) {
      this.adjList.set(vertex, []);
    }
  }

  addEdge(vertex, neighbor) {
    if (!this.adjList.has(vertex)) {
      this.adjList.set(vertex, []);
    }
    this.adjList.get(vertex).push(neighbor);
  }

  dfs(start) {
    const visited = new Set();
    this.dfsHelper(start, visited);
  }

  dfsHelper(vertex, visited) {
    visited.add(vertex);
    console.log(vertex);

    const neighbors = this.adjList.get(vertex);
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        this.dfsHelper(neighbor, visited);
      }
    }
  }
}

// Example usage
const graph = new Graph();

graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.addEdge("D", "F");
graph.addEdge("E", "F");

graph.dfs("A");

In this example, we define a Graph class that contains methods to add vertices and edges to the graph, and a dfs() method to perform the DFS algorithm.

The dfsHelper(vertex, visited) method is a recursive function that takes a vertex and a visited set as arguments. It adds the current vertex to the visited set, prints it to the console, and then recursively calls dfsHelper() on each of its unvisited neighbors.

The dfs(start) method initializes a visited set and then calls dfsHelper() with the start vertex as the starting point of the DFS traversal.

In the example usage, we create a new Graph object and add some vertices and edges to it. We then call the dfs() method on the graph, starting at vertex "A". The DFS algorithm will visit each vertex in the graph and print its value to the console. The output would be:

A
B
D
F
C
E

       A
     /   \
    B     C
   /       \
  D         E
   \       /
    F     F

In this graph, each vertex is represented by a letter (A-F), and each edge is represented by a line connecting the vertices. The graph has six vertices and six edges.

The Depth-First Search algorithm starts at vertex "A" and explores as far as possible along each branch before backtracking. In the visualization, the traversal order is shown by the order in which the vertices are visited: A -> B -> D -> F -> C -> E.

Time Complexity

The time complexity of the Depth-First Search (DFS) algorithm implemented in the previous example is O(V + E), where V is the number of vertices in the graph and E is the number of edges in the graph.

The DFS algorithm visits each vertex in the graph once, and visits each edge in the graph once. Therefore, the time complexity of the algorithm is proportional to the sum of the number of vertices and the number of edges in the graph.

In the implementation, we use an adjacency list to represent the graph, which allows us to access the neighbors of a given vertex in O(1) time on average. Therefore, the time complexity of the dfsHelper() method that visits the neighbors of a given vertex is proportional to the number of neighbors of that vertex.

In the worst case, when the graph is a complete graph, the time complexity of the algorithm is O(V^2). However, in most practical cases, the number of edges in the graph is much smaller than the number of vertices, so the time complexity is closer to O(V).

It's worth noting that the space complexity of the algorithm is also O(V + E), since we need to store the adjacency list and the visited set.

BFS vs. DFS

The time complexity of Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms are both O(V + E), where V is the number of vertices and E is the number of edges in the graph.

However, in practice, the performance of BFS and DFS can differ depending on the structure of the graph and the specific problem being solved. In general, BFS is often faster than DFS for finding the shortest path or the minimum number of steps required to reach a target node, since BFS always explores the nearest nodes first.

On the other hand, DFS can be faster than BFS for certain problems, such as finding connected components or detecting cycles in a graph, since DFS explores the graph in a more focused way and can terminate as soon as it finds a solution.

It's also worth noting that BFS uses more memory than DFS, since it maintains a queue of nodes to be visited, while DFS only needs to store the visited nodes and the call stack.

In summary, neither algorithm is universally faster than the other, and the choice between BFS and DFS depends on the specific problem and the structure of the graph.