leetcode——[133]Clone Graph克隆图

题目

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

示例：

输入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

提示：

1. 节点数介于 1 到 100 之间。
2. 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
3. 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
4. 必须将给定节点的拷贝作为对克隆图的引用返回。

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Example:

Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

1. The number of nodes will be between 1 and 100.
2. The undirected graph is a simple graph#Simple_graph), which means no repeated edges and no self-loops in the graph.
3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
4. You must return the copy of the given node as a reference to the cloned graph.

解题方法

BFS

广度优先搜索，用一个队列保存节点的邻居，用一个Map来保存遍历过的节点。

首先克隆传入的节点，然后从非空队列中取出节点，遍历节点的邻居节点，如果邻居节点没有被访问（被克隆），则添加邻居节点到队列中并克隆该邻居节点，然后向当前节点的克隆节点的neighbors添加邻居节点的克隆节点；如果邻居节点已经被访问（被克隆），则直接向当前节点的克隆节点的neighbors添加邻居节点的克隆节点。

这段代码跑了3ms，超过了96.38%的Java提交。

public class Solution {
    // Method 1 3ms 96.38%
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();		// store unvisited node
        queue.add(node);
        Node clone = new Node(node.val, new ArrayList<>());
        Map<Node, Node> map = new HashMap<>();    // store node and node's clone
        map.put(node, clone);
        while(!queue.isEmpty()) {
            Node cur = queue.poll();    // visit a node
            if (cur.neighbors != null) {
                for (Node neighbor : cur.neighbors) {
                    if (!map.containsKey(neighbor)) {    // neighbor node hasn't been cloned
                        queue.add(neighbor);    // add neighbor node into queue
                        map.put(neighbor, new Node(neighbor.val, new ArrayList<>()));    // clone the neighbor node
                    }
                    map.get(cur).neighbors.add(map.get(neighbor));    // add the neighbor node's clone into cur node's clone's neighbors
                }
            }
        }
        return clone;
    }
}

DFS

深度优先搜索，使用一个map保存节点与其克隆，用来判断节点是否被克隆，递归调用cloneGraph进行深度优先搜索。这段代码跑了3ms，超过了96.38%的Java提交。

public class Solution {
		// Method 2 3ms 96.38%
    Map<Node, Node> map = new HashMap<>();		// store node and node's clone
  
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Node clone = new Node(node.val, new ArrayList<>());
        map.put(node, clone);
        for (Node neighbor : node.neighbors) {
            if (!map.containsKey(neighbor)) {
                Node cloneNeighbor = cloneGraph(neighbor);    // recursive cloning first neighbor
                clone.neighbors.add(cloneNeighbor);    // add neighbor's clone into neighbors
            } else {
                clone.neighbors.add(map.get(neighbor));		// add neighbor's clone into neighbors
            }
        }
        return clone;
    }
}