Skip to content

Instantly share code, notes, and snippets.

@qiuwei
Last active July 2, 2017 21:32
Show Gist options
  • Save qiuwei/3d87088af27ca091275386faa1759412 to your computer and use it in GitHub Desktop.
Save qiuwei/3d87088af27ca091275386faa1759412 to your computer and use it in GitHub Desktop.
Clone Graph
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param node: A undirected graph node
* @return: A undirected graph node
*/
HashMap<UndirectedGraphNode, UndirectedGraphNode> oldToNew;
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) {
return null;
}
// write your code here
oldToNew = new HashMap<>();
HashSet<UndirectedGraphNode> visited = new HashSet<>();
dfs(node, visited);
bfs(node);
bfs(oldToNew.get(node));
return oldToNew.get(node);
}
private void bfs(UndirectedGraphNode node) {
HashSet<UndirectedGraphNode> visited = new HashSet<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
while(!queue.isEmpty()) {
UndirectedGraphNode current = queue.poll();
if(!visited.contains(current)) {
//System.out.println("current node is " + current.label);
visited.add(current);
for (UndirectedGraphNode n: current.neighbors){
queue.offer(n);
}
}
}
}
private void dfs(UndirectedGraphNode node, HashSet<UndirectedGraphNode> visited) {
if(visited.contains(node)) {
return;
} else {
UndirectedGraphNode newNode;
if(oldToNew.containsKey(node)) {
newNode = oldToNew.get(node);
} else {
newNode = new UndirectedGraphNode(node.label);
oldToNew.put(node, newNode);
}
for (UndirectedGraphNode child : node.neighbors) {
if(!oldToNew.containsKey(child)) {
UndirectedGraphNode newChild = new UndirectedGraphNode(child.label);
newNode.neighbors.add(newChild);
//newChild.neighbors.add(newNode);
oldToNew.put(child, newChild);
dfs(child, visited);
} else {
UndirectedGraphNode newChild = oldToNew.get(child);
//newChild.neighbors.add(newNode);
newNode.neighbors.add(newChild);
}
}
visited.add(node);
return;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment