LeetCode-133. 克隆图-Java-medium

题目链接

法一（BFS）

    /**
     * 法一（BFS）
     * 在BFS过程中克隆每一个节点
     *
     * @param node
     * @return
     */
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        Map<Node, Node> isClone = new HashMap<>(); // 记录节点是否已经被克隆，key为被克隆节点，value为克隆节点
        queue.offer(node);
        isClone.put(node, new Node(node.val));
        while (!queue.isEmpty()) {
            Node fromNode = queue.poll();
            List<Node> neighbors = fromNode.neighbors;
            Node fromNodeClone = isClone.get(fromNode);
            for (Node toNode : neighbors) {
                if (!isClone.containsKey(toNode)) { // 如果节点没有被克隆
                    queue.offer(toNode);
                    isClone.put(toNode, new Node(toNode.val));
                }
                fromNodeClone.neighbors.add(isClone.get(toNode)); // 克隆节点添加邻居
            }
        }
        return isClone.get(node); // 返回克隆图的第一个结点
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

法二（DFS）

    /**
     * 记录节点是否已经被克隆，key为被克隆节点，value为克隆节点
     */
    Map<Node, Node> isClone = new HashMap<>();

    /**
     * 法二（DFS）
     * 在DFS过程中克隆每一个节点
     * 由于图存在环，所以要标记访问过的结点，避免重复形成死循环
     *
     * @param node
     * @return
     */
    public Node cloneGraph_2(Node node) {
        if (node == null) {
            return null;
        }
        Node fromNodeClone = new Node(node.val, new ArrayList<>()); // 克隆node
        isClone.put(node, fromNodeClone); // 标记node已经被克隆
        for (Node toNode : node.neighbors) { // 枚举从node出发能到达的所有节点
            Node toNodeClone = isClone.get(toNode);
            if (toNodeClone == null) { // 如果toNode没有被克隆
                toNodeClone = cloneGraph_2(toNode); // dfs克隆toNode
            }
            fromNodeClone.neighbors.add(toNodeClone); // 克隆节点添加邻居
        }
        return fromNodeClone; // 返回克隆图的第一个结点
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

本地测试

        /**
         * 133. 克隆图
         */
        lay.showTitle(133);
        Solution133 sol133 = new Solution133();
        Integer[][] adjArr133 = new Integer[][]{{2, 4}, {1, 3}, {2, 4}, {1, 3}};
        List<List<Integer>> adjList133 = Arrays.stream(adjArr133).map(Arrays::asList).collect(Collectors.toList());
        undirectedGraph.Node firstVertex133 = undirectedGraphOpt.createGraph(adjList133);
        undirectedGraphOpt.BFSTraversal(firstVertex133);
        undirectedGraph.Node cloneVertex133_1 = sol133.cloneGraph(firstVertex133);
        undirectedGraphOpt.BFSTraversal(cloneVertex133_1);
        undirectedGraph.Node cloneVertex133_2 = sol133.cloneGraph_2(firstVertex133);
        undirectedGraphOpt.BFSTraversal(cloneVertex133_2);
1
2
3
4
5
6
7
8
9
10
11
12
13