Solution Developed In:

The Question

For this article we will be covering Leetcode's '133. Clone Graph' question.

Question:

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;
}

Explaining The Question

This Question is rated Medium. Which I believe is entirely accurate, so long as you have solid foundations in Graph Theory and it's applications. As well as ideally being skilled in either DFS or BFS algorithms.

Without knowing DFS or BFS algorithms, you will be unable to solve this problem. 😁

What we're being asked to do is to clone a graph. The idea is to create a new graph with the same nodes and edges as the original graph, but with the same values and neighbors WITHOUT referencing the original input graph.

Recommended Knowledge

1. Graph Theory
2. Adjacency List
3. Depth First Search (Recursive)
4. Breadth First Search (Optional)
5. Hash Map

What do we know?

1. We're given a reference to a node in a connected undirected graph that is represented with as an adjacency list in the input section.
2. We need to create a new graph with the same nodes and edges as the original graph, but with the same values and neighbors WITHOUT referencing the original input graph.

How we're going to do it:

We're going to recursively create this graph. The way we're going to do this is by using conducting a Depth First Search on the graph, at each node we visit we will create our own node (root) that is a copy of said node, and we will then add the old node to a hashmap (visited_nodes) to keep track of the nodes we've already visited. So we can prevent the duplication of nodes. Sometimes this is called Memoization.

At each node that we have not seen in the visited_nodes before we create it, we then conduct the same DFS on the neighbors of that node, which will return us a set of new nodes that we will add to the root node's neighbors list.

1. We're going to firstly create a visited_nodes hashmap to keep track of all of our visited nodes
2. We will then perform a Depth First Search (copy_graph) on all the nodes in the input graph, and we will create a new node for each node in the input graph.
3. In this Depth First Search we firstly ask 'Have we been to this node before?' if we have we will return the node that we have already created, if we have not we will create a new node and add it to the visited_nodes hashmap. This will make sense in just a second
4. So at this point, we have not visited this node, so we create it, and then we conduct a Depth First Search on the neighbors of this node, and we add the new nodes to the neighbors list of the root node.
5. Once the Depth First Search has been conducted on all the neighbors of the root node, we return the root node.
6. We do this to always return that newly created node, so we can add it to the neighbors list if called upon.

Big O Notation:

• Time Complexity: O(V + E) / O(n) | Where n is the number of nodes in the Matrix. V is the number of vertices in the graph. E is the number of edges in the graph as we're going to visit each vertex and each edge once. This is often represented as just O(n) as it's the number of nodes in the graph.
• Space Complexity: O(n) | Where n is the number of nodes in the Input graph as we will be using a hashmap to keep track of all the nodes we've already visited and at the same time storing the nodes of a given graph in the Call Stack due to the recursive Depth First Search.

The Big O Notation analysis for this problem is a little confusing as it combines a handful of different concepts all with their own Big O Notations. But in general, we reduce it down to the worst complexity being O(n). Feel free to correct me if you feel my analysis is wrong.

Leetcode Results:

See Submission Link:

• Runtime: 71 ms, faster than 79.16% of JavaScript online submissions for Clone Graph
• Memory Usage: 43.8 MB, less than 60.27% of JavaScript online submissions for Clone Graph.

The Solution

/**
 * Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {

    // Edge case 🤮
    // Empty node.
    if (!node) {
        return null;
    }

    // As all the nodes values are unique, we will use a hashmap
    // to store the visited nodes on the old graph.
    const node_map = new Map(); // Node.val -> Newly Created Node Address

    // We're going to recursively traverse the old graph and create new nodes
    // on the new graph. We do this by asking our hashmap if the current node
    // we plan on creating already exists within the hashmap? Meaning, we have already visited it.
    // If this is the case, we return the node already created.
    // If not, we create a new Node and add it to the hashmap (To prevent us from creating the same node twice).
    // We then iterate over all of the current nodes neighbors and recursively call our function.
    // Then we set it's returned result (Being either a new node or an already created node) as the current node's neighbors.
    const create_graph = (node) => {

        // Have we already visited this node?
        // If so return the node we already created.
        if (node_map.has(node.val)) {
            return node_map.get(node.val);
        }

        // So we have never visited this node before,
        // so create it, and add it to the hashmap to prevent us from creating it again.
        const root = new Node(node.val, []);
        node_map.set(node.val, root);

        // We now need to get all of this nodes neighbors for a fully deep clone.
        // So we're going to recursively call our function on each of the current nodes neighbors.
        // So it will create all of it's neighbors and then set them as the current node's neighbors.
        for (const neighbors of node.neighbors) {

            // Get my neighbors nodes, by creating them
            // or returning them if they already exist.
            const near_nodes = create_graph(neighbors);
            root.neighbors.push(near_nodes);
        }

        // Return the newly created node.
        // It can return at any point. 
        return root;
    };

    return create_graph(node);
};