https://leetcode.com/problems/clone-graph/
OJ's undirected graph serialization:
X. DFS
https://discuss.leetcode.com/topic/26560/java-solution-with-dfs-and-bfs
X. BFS
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
Use HashMap to look up nodes and add connection to them while performing BFS.
From: http://leetcode.com/2012/05/clone-graph-part-i.html we could use a hash table! As we copy a node, we insert it into the table. If we later find that one of a node’s neighbor is already in the table, we do not make a copy of that neighbor, but to push its neighbor’s copy to its copy instead. Therefore, the hash table would need to store a mapping of key-value pairs, where the key is a node in the original graph and its value is the node’s copy.
EPI Java Solution: Clone a graph
clone-graph.cc CloneGraph.java
public static class GraphVertex {
public int label;
public List<GraphVertex> edges;
public GraphVertex(int label) {
this.label = label;
edges = new ArrayList<GraphVertex>();
}
}
public static GraphVertex cloneGraph(GraphVertex g) {
if (g == null) {
return null;
}
Map<GraphVertex, GraphVertex> vertexMap = new HashMap<>();
LinkedList<GraphVertex> q = new LinkedList<GraphVertex>();
q.addLast(g);
vertexMap.put(g, new GraphVertex(g.label));
while (!q.isEmpty()) {
GraphVertex v = q.removeFirst();
for (GraphVertex e : v.edges) {
// Try to copy vertex e.
if (!vertexMap.containsKey(e)) {
vertexMap.put(e, new GraphVertex(e.label));
q.addLast(e);
}
// Copy edge v->e.
vertexMap.get(v).edges.add(vertexMap.get(e));
}
}
return vertexMap.get(g);
}
2. 设计数据结构 a.
List<Node> b.
Map<Node,Set<Node>>
c.Matrix[][]
1. 写两种能够表示directed graph的数据结构，不不保证connected，每个
node的值不不保证unique。⽤的数据结构做LC窈伞霰。
2. 复制⼀一个联通的有向图，先Recursive地写了了⼀一遍，然后问能不不能
iterative地写，用了个queue⼜又写了了⼀一遍⾮非递归的。问了了我为什什么要⽤用
map不不⽤用set，然后问了了时间空间复杂度，node和edge都要考虑
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/133_Clone_Graph.java
Clone an undirected graph. Each node in the graph contains a
label and a list of its neighbors.OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph
{0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by
#.- First node is labeled as
0. Connect node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
X. DFS
https://discuss.leetcode.com/topic/26560/java-solution-with-dfs-and-bfs
private Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
// DFS
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
if (map.containsKey(node)) return map.get(node);
UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
map.put(node, copy);
for (UndirectedGraphNode n : node.neighbors)
copy.neighbors.add(cloneGraph(n));
return copy;
} private HashMap<Integer, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
return clone(node);
}
private UndirectedGraphNode clone(UndirectedGraphNode node) {
if (node == null) return null;
if (map.containsKey(node.label)) {
return map.get(node.label);
}
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
map.put(clone.label, clone);
for (UndirectedGraphNode neighbor : node.neighbors) {
clone.neighbors.add(clone(neighbor));
}
return clone;
}
This question is the same as
copy list with random pointer.Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
- A queue is used to do breath first traversal.
- a map is used to store the visited nodes. It is the map between original node and copied node.
使用BFS来解决此问题。用一个Queue来记录遍历的节点，遍历原图，并且把复制过的节点与原节点放在MAP中防止重复访问。
图的遍历有两种方式，BFS和DFS
这里使用BFS来解本题，BFS需要使用queue来保存neighbors
但这里有个问题，在clone一个节点时我们需要clone它的neighbors，而邻居节点有的已经存在，有的未存在，如何进行区分？
这里我们使用Map来进行区分，Map的key值为原来的node，value为新clone的node，当发现一个node未在map中时说明这个node还未被clone，
将它clone后放入queue中处理neighbors。
使用Map的主要意义在于充当BFS中Visited数组，它也可以去环问题，例如A--B有条边，当处理完A的邻居node，然后处理B节点邻居node时发现A已经处理过了
处理就结束，不会出现死循环。
queue中放置的节点都是未处理neighbors的节点。
https://segmentfault.com/a/1190000003741052
广度优先搜索，同时用一个哈希表，将新旧节点映射起来。这样我们第一次遍历到的节点，我们会新建一个节点并映射到哈希表中。当以后再遍历到这个节点时，我们可以直接用哈希表取出它对应的新节点。我们只要保证，对于第一次遇到的图节点，我们都会建立一个克隆节点，并在哈希表映射起来就行了。
这里我们并不需要维护一个visited的集合，为什么呢？因为每次我们遇到一个之前没见过图节点，我们都会给它建立一个克隆节点，然后在哈希表中映射起来，并把这个图节点也放入队列中。所以只要哈希表中有这个图节点，就说明我们之前已经将该图节点放入队列了，就不需要再处理了。不过还是要把该图节点的克隆节点放入父克隆节点的邻居中。
https://discuss.leetcode.com/topic/18075/java-bfs-solutionpublic UndirectedGraphNode cloneGraph(UndirectedGraphNode root) {
if (root == null) return null;
// use a queue to help BFS
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
queue.add(root);
// use a map to save cloned nodes
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
// clone the root
map.put(root, new UndirectedGraphNode(root.label));
while (!queue.isEmpty()) {
UndirectedGraphNode node = queue.poll();
// handle the neighbors
for (UndirectedGraphNode neighbor : node.neighbors) {
if (!map.containsKey(neighbor)) {
// clone the neighbor
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
// add it to the next level
queue.add(neighbor);
}
// copy the neighbor
map.get(node).neighbors.add(map.get(neighbor));
}
}
return map.get(root);
}Use HashMap to look up nodes and add connection to them while performing BFS.
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap(); // origin node : copied node
UndirectedGraphNode myNode = new UndirectedGraphNode(node.label); // copy
map.put(node, myNode);
Queue<UndirectedGraphNode> q = new ArrayDeque(); // origin nodes
q.add(node);
// bfs traverse graph
while (!q.isEmpty()) {
UndirectedGraphNode cur = q.poll();
// all neighbors of current origin node
for (UndirectedGraphNode neighbor : cur.neighbors) {
// if the origin node is not visited
if (!map.containsKey(neighbor)) {
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
// to avoid loop, we just add the unvisited node to queue
q.offer(neighbor);
}
// add neighbors to the copied node
// copied node: map.get(cur) -> copied node of cur
// neighbors: map.get(neighbor) -> copied node of neighbor
map.get(cur).neighbors.add(map.get(neighbor));
}
}
return myNode;
}From: http://leetcode.com/2012/05/clone-graph-part-i.html we could use a hash table! As we copy a node, we insert it into the table. If we later find that one of a node’s neighbor is already in the table, we do not make a copy of that neighbor, but to push its neighbor’s copy to its copy instead. Therefore, the hash table would need to store a mapping of key-value pairs, where the key is a node in the original graph and its value is the node’s copy.
Node *clone(Node *graph) {
if (!graph) return NULL;
Map map;
queue<Node *> q;
q.push(graph);
Node *graphCopy = new Node();
map[graph] = graphCopy;
while (!q.empty()) {
Node *node = q.front();
q.pop();
int n = node->neighbors.size();
for (int i = 0; i < n; i++) {
Node *neighbor = node->neighbors[i];
// no copy exists
if (map.find(neighbor) == map.end()) {
Node *p = new Node();
map[node]->neighbors.push_back(p);
map[neighbor] = p;
q.push(neighbor);
} else { // a copy already exists
map[node]->neighbors.push_back(map[neighbor]);
}
}
}
return graphCopy;
}
public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node == null) return null; LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>(); UndirectedGraphNode newHead = new UndirectedGraphNode(node.label); queue.add(node); map.put(node, newHead); while(!queue.isEmpty()){ UndirectedGraphNode curr = queue.pop(); ArrayList<UndirectedGraphNode> currNeighbors = curr.neighbors; for(UndirectedGraphNode aNeighbor: currNeighbors){ if(!map.containsKey(aNeighbor)){ UndirectedGraphNode copy = new UndirectedGraphNode(aNeighbor.label); map.put(aNeighbor,copy); map.get(curr).neighbors.add(copy); queue.add(aNeighbor); }else{ map.get(curr).neighbors.add(map.get(aNeighbor)); } } } return newHead; } } |
clone-graph.cc CloneGraph.java
public static class GraphVertex {
public int label;
public List<GraphVertex> edges;
public GraphVertex(int label) {
this.label = label;
edges = new ArrayList<GraphVertex>();
}
}
public static GraphVertex cloneGraph(GraphVertex g) {
if (g == null) {
return null;
}
Map<GraphVertex, GraphVertex> vertexMap = new HashMap<>();
LinkedList<GraphVertex> q = new LinkedList<GraphVertex>();
q.addLast(g);
vertexMap.put(g, new GraphVertex(g.label));
while (!q.isEmpty()) {
GraphVertex v = q.removeFirst();
for (GraphVertex e : v.edges) {
// Try to copy vertex e.
if (!vertexMap.containsKey(e)) {
vertexMap.put(e, new GraphVertex(e.label));
q.addLast(e);
}
// Copy edge v->e.
vertexMap.get(v).edges.add(vertexMap.get(e));
}
}
return vertexMap.get(g);
}
2. 设计数据结构 a.
List<Node> b.
Map<Node,Set<Node>>
c.Matrix[][]
1. 写两种能够表示directed graph的数据结构，不不保证connected，每个
node的值不不保证unique。⽤的数据结构做LC窈伞霰。
2. 复制⼀一个联通的有向图，先Recursive地写了了⼀一遍，然后问能不不能
iterative地写，用了个queue⼜又写了了⼀一遍⾮非递归的。问了了我为什什么要⽤用
map不不⽤用set，然后问了了时间空间复杂度，node和edge都要考虑
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/133_Clone_Graph.java
