LeetCode 133. Clone Graph

Problem

LeetCode 138. Copy List with Random Pointer

1. 题目简述

给出无向连通图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。必须将 给定节点的拷贝 作为对克隆图的引用返回。

Examples：

2. 算法思路

这道题和LeetCode 138. Copy List with Random Pointer是基本一致的，稍微有所变形，而且涉及到DFS和BFS。

目前的困境是一样的，我们每次在创建节点后，对neighbor进行遍历时，无法直接找到对应的节点，依然用hashMap来存储是比较直接的方式。

哈希表+DFS

哈希表+BFS

双队列+DFS

O(1)空间复杂度的方法

3. 解法

HashMap + DFS

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    Map<Node, Node> clone = new HashMap();

    public Node cloneGraph(Node node) {
        if (clone.containsKey(node)) {
            return clone.get(node);
        }

        Node newNode = new Node(node.val);
        clone.put(node, newNode);

        for (Node neighbor : node.neighbors) {
            newNode.neighbors.add(cloneGraph(neighbor));
        }

        return clone.get(node);
    }
}

HashMap + BFS

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        Map<Node, Node> clone = new HashMap();
        Node newNode = new Node(node.val);
        Queue<Node> queue = new LinkedList();
        queue.offer(node);
        clone.put(node, newNode);

        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            for (Node neighbor : temp.neighbors) {
                if (!clone.containsKey(neighbor)) {
                    clone.put(neighbor, new Node (neighbor.val));
                    queue.offer(neighbor));
                }
                clone.get(temp).neighbors.add(clone.get(neighbor));
            }
        }

        return newNode;
    }
}

双Queue

   // 这种双queue的做法一开始不行，原因在于，每次BFS遍历到一个老节点时，遍历其neighbors，对于我们copy的那个节点，我们没办法从newQueue里面获取到，所以不能用简单的isVisited的boolean数组来替代，而是用Node数组来访问。
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        Node[] allNodes = new Node[101];
        Arrays.fill(allNodes, null);

        Queue<Node> oldQueue = new LinkedList();
        Queue<Node> newQueue = new LinkedList();

        oldQueue.offer(node);
        Node ret = new Node(node.val);
        newQueue.offer(ret);
        allNodes[1] = ret;

        while (!oldQueue.isEmpty()) {
            Node oldOne = oldQueue.poll();
            Node newOne = newQueue.poll();
            for (Node neighbor : oldOne.neighbors) {
                if (allNodes[neighbor.val] == null) {
                    // Create new node.
                    Node newNode = new Node(neighbor.val);
                    allNodes[neighbor.val] = newNode;
                    oldQueue.offer(neighbor);
                    newQueue.offer(newNode);
                }
                newOne.neighbors.add(allNodes[neighbor.val]);
            }
        }

        return ret;
    }
}