Clone a Graph: Depth First Search (DFS)

Mark as Completed

Lesson

Implement depth-first traversal for an undirected graph in JavaScript.

Write a function called depthFirstTraversal
that takes in a starting node as an input and traverses the entire graph using depth-first search. The function should initialize a visited array and use a helper function to keep track of the visited nodes while traversing through the graph. The helper function should use recursion to go through all the adjacent vertices of each node.

Example:

const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'D');
graph.addEdge('D', 'A');
depthFirstTraversal(graph, 'A');

// A B C D

Walkthrough

To implement depth-first traversal, we need to initialize a visited array and use a helper function to keep track of the visited nodes. We will use recursion to traverse through all the adjacent vertices of each node.

First, we initialize an empty array called visitedNodes
to keep track of the visited nodes. Then we loop through all the vertices in the graph and set their visited value to false. We call the helper function dfsHelper
and pass in the starting node and the visited array.In the helper function, we set the visited value of the current node to true, log the node, and get its neighbors. We loop through each neighbor and check if it has been visited or not. If it has not been visited, we call the dfsHelper
function again with the new node and mark it as visited.

Here's the code:

function depthFirstTraversal(graph, start) {
  const visitedNodes = [];

  for (let i = 0; i < graph.vertices.length; i++) {
    visitedNodes[graph.vertices[i]] = false;
  }

  dfsHelper(start, visitedNodes);

  function dfsHelper(node, visited) {
    visited[node] = true;
    console.log(node);

    const neighbors = graph.list.get(node);
    for (let i = 0; i < neighbors.length; i++) {
      const neighbor = neighbors[i];
      if (!visited[neighbor]) {
        dfsHelper(neighbor, visited);
      }
    }
  }
}

Big O Complexity Analysis:

The time complexity of depth-first traversal for an undirected graph is O(V+E), where V is the number of vertices and E is the number of edges. This is because we visit each vertex once and each edge twice.

The space complexity of the algorithm is O(V), where V is the number of vertices, as we need to keep track of which nodes have been visited.

The time complexity of the dfsHelper
function is O(E), where E is the number of edges, as we traverse through all the edges in the graph. The space complexity of the dfsHelper
function is O(V), where V is the number of vertices, as we need to keep track of the visited nodes.

Previous Lesson Next Lesson