anybody say say cisco?# Stock
g*b
1 楼
第一遍抄的网上的BFS写法
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
UndirectedGraphNode cnode = new UndirectedGraphNode(node.label);
Map visited = new HashMap<
UndirectedGraphNode, UndirectedGraphNode>();
visited.put(node, cnode);
Queue queue = new LinkedList<
UndirectedGraphNode>();
queue.add(node);
while(!queue.isEmpty()){
UndirectedGraphNode cur = queue.poll();
for(UndirectedGraphNode n : cur.neighbors){
if(visited.keySet().contains(n)){
visited.get(cur).neighbors.add(visited.get(n));
}else{
UndirectedGraphNode cn = new UndirectedGraphNode(n.label
);
visited.put(n, cn);
visited.get(cur).neighbors.add(cn);
queue.add(n);
}
}
}
return cnode;
}
第二遍自己写的时候，写了recursive function。仔细想了想觉得和BFS没有本质区别
，实际时间也差不多，不知道自己有没有想岔？求指导。
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
Map map = new HashMap<
UndirectedGraphNode, UndirectedGraphNode>();
return cloneNode(node, map);
}
private UndirectedGraphNode cloneNode(UndirectedGraphNode node, Map<
UndirectedGraphNode, UndirectedGraphNode> map) {
UndirectedGraphNode copy;
if(map.keySet().contains(node)){
copy = map.get(node);
}else{
copy = new UndirectedGraphNode(node.label);
map.put(node, copy);
}
for(UndirectedGraphNode n : node.neighbors){
if(map.keySet().contains(n)) copy.neighbors.add(map.get(n));
else copy.neighbors.add(cloneNode(n, map));
}
return copy;
}
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
UndirectedGraphNode cnode = new UndirectedGraphNode(node.label);
Map
UndirectedGraphNode, UndirectedGraphNode>();
visited.put(node, cnode);
Queue
UndirectedGraphNode>();
queue.add(node);
while(!queue.isEmpty()){
UndirectedGraphNode cur = queue.poll();
for(UndirectedGraphNode n : cur.neighbors){
if(visited.keySet().contains(n)){
visited.get(cur).neighbors.add(visited.get(n));
}else{
UndirectedGraphNode cn = new UndirectedGraphNode(n.label
);
visited.put(n, cn);
visited.get(cur).neighbors.add(cn);
queue.add(n);
}
}
}
return cnode;
}
第二遍自己写的时候，写了recursive function。仔细想了想觉得和BFS没有本质区别
，实际时间也差不多，不知道自己有没有想岔？求指导。
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
Map
UndirectedGraphNode, UndirectedGraphNode>();
return cloneNode(node, map);
}
private UndirectedGraphNode cloneNode(UndirectedGraphNode node, Map<
UndirectedGraphNode, UndirectedGraphNode> map) {
UndirectedGraphNode copy;
if(map.keySet().contains(node)){
copy = map.get(node);
}else{
copy = new UndirectedGraphNode(node.label);
map.put(node, copy);
}
for(UndirectedGraphNode n : node.neighbors){
if(map.keySet().contains(n)) copy.neighbors.add(map.get(n));
else copy.neighbors.add(cloneNode(n, map));
}
return copy;
}
