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
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching

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 that each node must maintain (we represent our graph as an adjacency list).

Without the result it is O( | V | ) because we will store V vertices in the hashtable (and the queue can hold at worst some fractional multiple of the total number for vertices...imagine 1 node connected to 9 nodes all at once in a graph of size 10...and we start from that 1 node. Our queue would have 9 nodes in it at once on the first iteration).

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: https://www.youtube.com/user/tusharroy2525

GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: https://www.youtube.com/user/VSympathyV

Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is number 19.5 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

Видео Clone An Undirected Graph - The Utility of Hashtable Mappings ("Clone Graph" on Leetcode) канала Back To Back SWE