Clone Graph
In a connected, undirected graph each node is an object with a number val and a list neighbors that holds the node objects it is connected to. Your job is to make a deep copy: a brand-new graph with the same values and the same connections, in which no node object is shared with the original (every neighbors list must point at copies, never at original nodes).
class Node {
constructor(val, neighbors = []) { this.val = val; this.neighbors = neighbors; }
}The tests describe a graph with an adjacency list adjList: node i + 1 has the neighbours adjList[i], listed in that order, and node 1 is the entry point. An empty adjList is an empty graph. Your function cloneGraph(adjList) should
- build the original
Nodegraph fromadjList, - deep-copy it, starting from node 1, and
- return the adjacency list of the copy in the same format (the neighbour order must be preserved).
In JavaScript the starter provides Node, buildGraph (step 1) and toAdjList (step 3), and checks that you did not simply return the original: you only write cloneNode(node). In Python, define a small Node class and those two steps yourself. Only the returned adjacency list is compared by the tests, but the copy must be a real deep copy.
Constraints
0 <= number of nodes <= 100- Node values are
1..nand distinct; there are no self-loops or repeated edges. - The graph is connected, and edges are undirected: if
bis in the list ofa, thenais in the list ofb.
Examples
Example 1
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]]
A square: node 1 touches 2 and 4, node 2 touches 1 and 3, and so on. The clone must have the same four nodes with the same neighbour lists.
Example 2
Input: adjList = [[]] Output: [[]]
A single node with no neighbours.
Example 3
Input: adjList = [] Output: []
An empty graph has no nodes at all, so the clone is empty too.
JavaScript you'll use: Map and Set Graphs and grids in JavaScript Classes for data structures
class Node {
constructor(val, neighbors = []) {
this.val = val;
this.neighbors = neighbors;
}
}
/** Builds the graph described by adjList (node i + 1 has neighbours adjList[i]) and returns node 1, or null. */
function buildGraph(adjList) {
const nodes = adjList.map((_, i) => new Node(i + 1));
adjList.forEach((list, i) => list.forEach((v) => nodes[i].neighbors.push(nodes[v - 1])));
return nodes.length ? nodes[0] : null;
}
/** Reads a graph back into an adjacency list (index = val - 1), keeping each neighbour order. */
function toAdjList(start) {
const byVal = new Map();
const stack = start ? [start] : [];
while (stack.length) {
const node = stack.pop();
if (byVal.has(node.val)) continue;
byVal.set(node.val, node.neighbors.map((nb) => nb.val));
for (const nb of node.neighbors) stack.push(nb);
}
return Array.from({ length: byVal.size }, (_, i) => byVal.get(i + 1));
}
/**
* Write this: return a deep copy of the graph that contains `node` (null for no graph).
* @param {Node | null} node
* @return {Node | null}
*/
function cloneNode(node) {
}
// The tests call this one. Keep it as is.
function cloneGraph(adjList) {
const original = buildGraph(adjList);
const copy = cloneNode(original);
if (original !== null && copy === original) throw new Error("cloneNode returned the original node, not a copy");
return toAdjList(copy);
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.