707672. Clone an Undirected Graph
Medium
Clone an Undirected Graph
Slug: clone-graph
Difficulty: Medium
Id: 707672
Topic Tags: Graph, DFS, BFS
Company Tags: Google
Summary
Clone an undirected graph. Given a reference graph and an integer array representing a connected set of nodes in the given graph, return a deep copy (clone) of the given graph.
Detailed Explanation
To solve this problem, we will create a new graph with all the same nodes as the original graph. For each node in the original graph, we will add it to our new graph and then recursively add all its neighbors. This process is similar to how you would perform a depth-first search (DFS) or breadth-first search (BFS) on a graph.
Here's the step-by-step breakdown of the solution:
- Create an empty graph with the same number of nodes as the original graph.
- Iterate over each node in the original graph.
- For each node, create a new node in our new graph and add it to the set of visited nodes.
- Recursively visit all the neighbors of the current node (i.e., its children) in the original graph.
- When visiting a neighbor, check if it has been visited before. If not, mark it as visited and recursively visit all its neighbors.
- Continue this process until we have visited all nodes in the original graph.
Time complexity for this algorithm is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.
Optimized Solutions
Java
class Node {
int val;
List<Node> neighbors;
public Node(int val) {
this.val = val;
this.neighbors = new ArrayList<>();
}
}
public class Solution {
public Node cloneGraph(Node node, HashMap<Integer, Node> map) {
if (node == null) return null;
if (map.containsKey(node.val)) return map.get(node.val);
Node newNode = new Node(node.val);
map.put(node.val, newNode);
for (Node neighbor : node.neighbors) {
newNode.neighbors.add(cloneGraph(neighbor, map));
}
return newNode;
}
}