算法

(BFS) $O(n)$

BFS遍历图

Java 代码

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }
        // map保存已访问的图节点
        HashMap<Node, Node> map = new HashMap<>();
        // 使用队列，BFS遍历图
        Queue<Node> queue = new LinkedList<>();

        // 维护map和queue
        queue.offer(node);
        map.put(node, new Node(node.val));

        // 开始BFS遍历
        while (!queue.isEmpty()) {
            // 取队首节点，查看邻接节点
            Node graphNode = queue.poll();
            for (Node neighbor : graphNode.neighbors) {
                // 针对当前neighbor节点，对比map中元素，没有则保存到map中
                if (!map.containsKey(neighbor)) {
                    // K：原图中节点，V：复制节点
                    map.put(neighbor, new Node(neighbor.val));
                    queue.offer(neighbor);
                }
                // 更新map中已保存节点的V值，即复制
                map.get(graphNode).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);   
    }
}