[LintCode/LeetCode] Clone Graph [BFS/DFS]

102 查看

Problem

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

return a deep copied graph.

Example

How we serialize an undirected graph.
Nodes are labeled uniquely.
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 node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

Note

开始看这道题目的时候,没有看懂queue和hashmap的作用。
复制一个无向图,先分析图的结构:label相当于图结点的value,而neighbors相当于图结点的所有next。然后考虑用什么方式复制:用queue用来标记当前正在复制的或已经复制过的结点cur,而hashmap用来进行对新建无向图结点root进行复制labelneighbors的操作。首先,从node结点开始,放入queue。然后对这个放入queue的结点cur开始操作:遍历cur的所有neighbors,当前遍历到的的neighbors叫做next。若map中不存在这个点,即没有被复制过,就在map中复制这个结点nextlabel,同时存入queue以便在下次循环取出并复制其neighbors;无论map中包不包含这个neighbors结点next,都要将next加入map中对应新建结点rootneighbors。当BFS完成,则queue中没有新的结点了,退出while循环。返回在map中更新过的root,结束。
map.get(cur).neighbors.add(map.get(next));
这一句可以理解为,在for循环对curneighbors的遍历中,先在HashMap里的root中建立新结点next,再将next放进root的结点curneighbors里。

Solution

// Definition for undirected graph.
class UndirectedGraphNode {
    int label;ArrayList<UndirectedGraphNode> neighbors;
    UndirectedGraphNode(int x) { 
        label = x; 
        neighbors = new ArrayList<UndirectedGraphNode>(); 
    }
}
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        UndirectedGraphNode root = new UndirectedGraphNode(node.label);//复制根节点
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        queue.offer(node);//queue放入根结点
        map.put(node, root);//map放入根结点和它的复制结点
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();//取出queue中(同一层)的结点进行BFS
            for (UndirectedGraphNode n: cur.neighbors) {
                //对没有复制过的结点进行复制,并将这个结点放入queue
                if (!map.containsKey(n)) {
                    map.put(n, new UndirectedGraphNode(n.label));
                    queue.offer(n);
                }
                //连接复制结点和复制neighbor结点
                map.get(cur).neighbors.add(map.get(n));
            }
        }
        return root;
    }
}

DFS


public class Solution {
   public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        return cloneNode(node, map);
    }
    private UndirectedGraphNode cloneNode(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
        if (node == null) return node;
        if (map.containsKey(node)) {
            return map.get(node);
        } else {
            UndirectedGraphNode nodeCopy = new UndirectedGraphNode(node.label);
            map.put(node, nodeCopy);
            for (UndirectedGraphNode child : node.neighbors) {
                nodeCopy.neighbors.add(cloneNode(child, map));
            }
            return nodeCopy;
        }
    }
}

2019 - 知识虫 - 我的知识库 重庆启连科技有限公司 渝ICP备16002641号-2

渝公网安备 50010702501581号