Make a deep copy of an undirected graph, there could be cycles in the original graph.
Assumptions
- The given graph is not null
DFS
/*
* class GraphNode {
* public int key;
* public List<GraphNode> neighbors;
* public GraphNode(int key) {
* this.key = key;
* this.neighbors = new ArrayList<GraphNode>();
* }
* }
*/
public class Solution {
public List<GraphNode> copy(List<GraphNode> graph) {
// Write your solution here.
Map<GraphNode, GraphNode> map = new HashMap<>();
for (GraphNode node : graph) {
if (!map.containsKey(node)) {
map.put(node, new GraphNode(node.key));
}
dfs(node, map);
}
return new ArrayList<>(map.values());
} private void dfs(GraphNode node, Map<GraphNode, GraphNode> map) {
GraphNode newNode = map.get(node);
for (GraphNode gNode : node.neighbors) {
if (!map.containsKey(gNode)) {
map.put(gNode, new GraphNode(gNode.key));
}
newNode.neighbors.add(map.get(gNode));
}
}
}
BFS
/*
* class GraphNode {
* public int key;
* public List<GraphNode> neighbors;
* public GraphNode(int key) {
* this.key = key;
* this.neighbors = new ArrayList<GraphNode>();
* }
* }
*/
public class Solution {
public List<GraphNode> copy(List<GraphNode> graph) {
// Write your solution here.
Map<GraphNode, GraphNode> map = new HashMap<>();
for (GraphNode gNode: graph) {
map.put(gNode, new GraphNode(gNode.key));
}
for (GraphNode node : graph) {
GraphNode cpNode = map.get(node);
for (GraphNode nei: node.neighbors) {
cpNode.neighbors.add(map.get(nei));
}
}
return new ArrayList<>(map.values());
}
}