Clone An Undirected Graph - The Utility of Hashtable Mappings ("Clone Graph" on Leetcode)

Free 5-Day Mini-Course: https://backtobackswe.com Try Our Full Platform: https://backtobackswe.com/pricing 📹 Intuitive Video Explanations 🏃 Run Code As You Learn 💾 Save Progress ❓New Unseen Questions 🔎 Get All Solutions Question: Design an algorithm that takes a reference to a vertex u, and creates a copy of the graph on the vertices reachable from u. Return the copy of u (as it is the entry to the cloned section of the graph we will have just created). The Approach When we clone a structure like a graph or linked list we will use a hashtable to assist in the cloning. We will map each node or structure to its corresponding clone. We will clone in a breadth-first manner so we can fill out all of the adjacent relationships in the cloned graph. This means we will use a queue. (Queue for BFS, Stack for DFS. This is because each data structure enforces how nodes are searched). The Algorithm Add the start node the caller gave us to the queue and map the node to its clone through the hashtable. We will continue the cloning until the queue is empty (there will be no more nodes to process). We then pull a node from the queue, call it currVertex. We will iterate all of currVertex's adjacent nodes, call each object yielded adjVertex. Do we create a cloned node for adjVertex? If the adjVertex is NOT in the hashtable create a mapping for adjVertex (adjVertex to its value clone, as described before) and add adjVertex to the queue since it needs its adjacent nodes mapped out in the cloned graph. Add the cloned node of adjVertex as an adjacent node to the cloned node of currVertex. Complexities V is the number of vertices in the graph section that is cloned. E the number of adjacent edges coming off vertices. Time: O( | V | + | E | ) We will touch V nodes and traverse E edges. Space: O( | V | + | E | ) The cloned graph we return (if we include it in the space complexity) will be the sum of the space of the cloned vertices and edge relationships th