Implement a breadth-first traversal function for an undirected graph in JavaScript. Given a graph and a starting node, the function should traverse the graph in a breadth-first manner, copying each visited node along the way. The function should return an array of all the visited nodes.

Example:

const graph = {
  vertices: 4,
  adjacentList: {
    a: ['b', 'c'],
    b: ['a', 'd'],
    c: ['a', 'd'],
    d: ['b', 'c']
  }
};

breadthFirstTraversal(graph, 'a');

// ['a', 'b', 'c', 'd']

Walkthrough

To implement a breadth-first traversal function for an undirected graph, we will use a queue to keep track of the unvisited nodes. We will initialize a visited array, which will store the nodes that we have already visited. We will start at the given starting node and add it to the queue. We will then enter a loop that continues as long as the queue is not empty. During each iteration, we will dequeue the next node from the queue and mark it as visited. We will then add all its unvisited neighbors to the queue, one by one.

Here is the implementation:

function breadthFirstTraversal(graph, startingNode) {
  const visitedNodes = [];
  const queue = [];

  // Mark all nodes as unvisited
  for (let i = 0; i < graph.vertices; i++) {
    visitedNodes[i] = false;
  }

  // Add the starting node to the queue and mark it as visited
  queue.push(startingNode);
  visitedNodes[startingNode] = true;

  while (queue.length > 0) {
    // Dequeue a node from the queue and add it to the visited array
    const currentNode = queue.shift();
    visitedNodes.push(currentNode);

    // Get all unvisited neighbors of the current node and add them to the queue
    const neighbors = graph.adjacentList[currentNode];
    for (let i = 0; i < neighbors.length; i++) {
      const neighbor = neighbors[i];
      if (!visitedNodes[neighbor]) {
        visitedNodes[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }

  return visitedNodes;
}

Big O Complexity Analysis:

The time complexity of the algorithm is O(V+E), which is the same as the time complexity of BFS on a graph. We visit each vertex and each edge exactly once, which takes O(V+E) time.

The space complexity of the algorithm is also O(V+E), since we need to store the visited array and the queue. The visited array takes O(V) space, while the queue takes O(E) space in the worst case, where E is the number of edges in the graph. Therefore, the total space complexity is O(V+E).