Given a graph data structure where each node contains a label and a list of its neighbors, write a function to clone an undirected graph.

Walkthrough

In order to clone a graph, we will need to traverse through the input graph and rebuild it. We can do this using a depth-first search (DFS) or a breadth-first search (BFS) algorithm.

First, we will create a function that takes in a node from the original graph and a dictionary to store visited nodes. The function will create a new node with the same label as the original node and an empty array for its neighbors. Then, it will mark the original node as visited and iterate through its neighbors. For each neighbor, it will check if it has already been visited by checking if it exists in the visited dictionary. If it has not been visited, the function will call itself recursively with the neighbor as the input node and add the returned node to the new node's neighbors array. If the neighbor has already been visited, the function will add the neighbor's corresponding node in the new graph to the new node's neighbors array.

After creating the function, we will initialize the visited dictionary and call the function with the input node from the original graph. The returned node will be the starting node for the new graph, which we will return as the final output.

Here is the implementation of the solution:

function cloneGraph(node) {
  const visited = {};

  const dfs = (originalNode) => {
    const newNode = {
      label: originalNode.label,
      neighbors: []
    };
    visited[originalNode.label] = newNode;

    for (let i = 0; i < originalNode.neighbors.length; i++) {
      const neighbor = originalNode.neighbors[i];
      if (!visited[neighbor.label]) {
        const newNeighbor = dfs(neighbor);
        newNode.neighbors.push(newNeighbor);
      } else {
        newNode.neighbors.push(visited[neighbor.label]);
      }
    }
    return newNode;
  };

  return dfs(node);
}

Big O Complexity Analysis:

The time complexity of this solution is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because the algorithm visits each vertex once and each edge twice (once for each neighbor of each vertex).

The space complexity of this solution is also O(V + E) because we need to store a copy of each vertex and edge in the new graph, as well as the visited dictionary to avoid visiting the same node multiple times.