133. Clone Graph (Medium) Google Facebook Uber PocketGems

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 #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. 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
         / \
         \_/

Solution 1: BFS + HashMap O(n + m); O(n) n is # of nodes

    /**
     * BFS O(n + m);O(n)
     * Use map<Integer, UndirectedGraphNode> to represent the new graph and a visited set.
     * For each visit, connect the node with neighboring nodes.
     * If neighboring nodes not in new graph yet, need to create them.
     * Visit:
     * Check whether current label is in new graph:
     * | If not, create a new node with current label and put in map.
     * If neighbors exist:
     * | For each neighbor:
     * |   If its not visited, add it to queue and create a new node.
     * |   Connect current node with this neighbor.
     */
    public UndirectedGraphNode cloneGraphB(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }

        Map<Integer, UndirectedGraphNode> map = new HashMap<>();
        UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
        map.put(node.label, clone);

        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        queue.offer(node); //store old nodes
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            for (UndirectedGraphNode neighbor : cur.neighbors) { //neighbors of old nodes
                if (!map.containsKey(neighbor.label)) {
                    // copy nodes(neighbors), store the old->new mapping information in HashMap
                    map.put(neighbor.label, new UndirectedGraphNode(neighbor.label));
                    queue.offer(neighbor); //store visited neighbors
                }
                map.get(cur.label).neighbors.add(map.get(neighbor.label));//copy edges, connect cur with its neighbors
            }
        }
        return clone;
    }

    class UndirectedGraphNode { //无向图的表示方法，要会
        int label;
        List<UndirectedGraphNode> neighbors;

        UndirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<>();
        }
    }

Solution 2: DFS + HashMap O(n + m); O(n) 要会

    /**
     * DFS
     * Statement: Given a node, and a graph map to build, return the cloned node.
     * Sub-problem: Build neighbors.
     * Complete task: Build current node. Build neighbors. Connect current node with its neighbors.
     * Base case: If current node is null, return null.
     * Implementation:
     * For each node in original node's neighbors:
     * | If new graph doesn't have it:
     * |   DFS to copy it and add returned copy node to clone's neighbor.
     * | If already have, means it's built:
     * |   Add it to clone's neighbor.
     * Return cloned node.
     */
    Map<Integer, UndirectedGraphNode> map = new HashMap<>();

    public UndirectedGraphNode cloneGraph(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(cloneGraph(neighbor));
        }
        return clone;
    }

Follow Up:

1.Graph里面不一定所有node都相连，但是基本思路一样，被面试官指出了一个bug。。。希望不会影响听说最近bar高了

图不连通和连通的区别：连通只要给一个node就能克隆，不连通给一个node不能克隆。所以自己还要写一个Graph类包括了所有点的集合，输入参数从一个node变为一个图（不连通）。

2.节点值可能重复 （和学长mock时遇到这个变种）

Map的key要改成original node的引用，其他代码一样 https://www.geeksforgeeks.org/clone-an-undirected-graph/

    public UndirectedGraphNode cloneGraphC(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        // use a map to save cloned nodes 将key从Integer改成UndirectedGraphNode
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        // clone the root
        map.put(node, new UndirectedGraphNode(node.label));

        // use a queue to help BFS
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            // handle the neighbors
            for (UndirectedGraphNode neighbor : cur.neighbors) {
                if (!map.containsKey(neighbor)) { //将neighbor.label改成neighbor
                    // clone the neighbor
                    map.put(neighbor, new UndirectedGraphNode(neighbor.label));
                    // add it to the next level
                    queue.offer(neighbor);
                }
                // copy the edge
                map.get(cur).neighbors.add(map.get(neighbor)); //cur.label改成cur
            }
        }

        return map.get(node);
    }

3.dfs改迭代