LeetCode 133. Clone Graph

The Problem

Link to original problem on LeetCode.

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
public int val;
public List<Node> neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Examples Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Constraints
  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops in the graph.
  • The Graph is connected and all nodes can be visited starting from the given node.

My Solution

For all of the below solutions, this is the definition of Node that we'll use:

class Node {
val: number
neighbors: Node[]
constructor(val?: number, neighbors?: Node[]) {
this.val = (val===undefined ? 0 : val)
this.neighbors = (neighbors===undefined ? [] : neighbors)
}
}

Our depth-first search creates a Map to store the unique Node values and a reference to the relevant cloned Node. This will allow us to create new Nodes and access them without getting stuck in a loop of recreating the same Nodes again and again.

We define a function clone that takes a Node and checks the Map to see if we've made a clone of it yet. If so, we just return the clone that's in our Map. Otherwise, we need to create that clone Node. First we set a new key-value pair in the Map, using the Node's value as the key and creating a new Node from that original Node's value.

We immediately retrieve that key-value pair, and then set the cloned Node's neighbors property to be equal to a new array of the original Node's neighbors passed recursively to the clone function. Because we're using our Map to keep track of cloned Nodes, no Node will get cloned more than once. If a Node has already been cloned, we just return that Node from the Map. We do this step separately from adding the newly-cloned Node to the Map because we otherwise get stuck in a loop—the new Node would not be added to the Map until it was done recursing over the array of neighbors, but the recusion cannot terminate if it never finds cloned Nodes in the Map.

Finally, we can call clone(node) to kick off our recursive depth-first search to recreate the graph.

You could achieve the same result without creating the clone function if, instead, you modified the function arguments to accept an optional Map. Then you would pass the Map we initially create directly into the recursive calls, instead of having it live in the lexical scope of the clone function.

function cloneGraph(node: Node | null): Node | null {
if (node === null) return null;

const graph = new Map<Node, Node>();

const clone = root => {
if (!graph.has(root)) {
graph.set(root, new Node(root.val));
graph.get(root).neighbors = root.neighbors.map(clone);
}
return graph.get(root);
}

return clone(node);
};

Unlike our depth-first search, the breadth-first search is iterative rather than recursive. Again we create a Map to keep track of nodes we've visited. But now we also create a queue to keep track of Nodes for which we need to add their neighbors to the cloned graph.

As long as there are Nodes in the queue, we will shift the first item out of the queue to process it. For each neighbor in that Node, we'll see if the neighbor already exists in the Map. If not, we add the neighbor Node to the Map and to the queue to process its neighbors. Finally, we add each of the cloned neighbor nodes to the neighbors property of the Node we pulled from our queue.

Once the queue is empty, we've traversed the graph and cloned every Node. We just need to return the first cloned Node from our Map to return the new graph.

function cloneGraph(node: Node | null): Node | null {
if (node === null) return null;

const graph = new Map<Node, Node>();
graph.set(node, new Node(node.val));
const queue: Node[] = [node];
while (queue.length) {
const currentNode = queue.shift();
currentNode.neighbors.forEach(neighbor => {
if (!graph.has(neighbor)) {
graph.set(neighbor, new Node(neighbor.val));
queue.push(neighbor);
}
graph.get(currentNode).neighbors.push(graph.get(neighbor));
})
}
return graph.get(node);
};