Java算法题-解析克隆图问题

题目

给定一个无向图，它的节点被分为两部分：节点本身和节点的邻居。我们需要为每个节点创建一个新的节点，并使新节点与原节点的邻居关系相同。

引言

今天，我们将探讨一个有趣的图问题——克隆图。在这个问题中，我们需要复制一个无向图，返回其深拷贝（克隆）。这看似简单的问题实际上涉及到图的遍历和深度优先搜索等知识点。

算法思路

这个问题可以通过深度优先搜索（DFS）来解决。具体思路如下：

1. 创建一个哈希表 visited，用于存储原节点和克隆节点的映射关系。
2. 从图的任意节点开始遍历，遍历过程中使用DFS，逐个克隆节点。
3. 当遍历到一个节点时，首先检查该节点是否已经被克隆。如果已经被克隆，则直接返回克隆节点；如果尚未被克隆，则创建一个新的节点，将其加入哈希表，并将原节点的邻居递归克隆并加入新节点的邻居中。

代码实现

以下是使用 Java 实现的解决方案：

import java.util.HashMap;
import java.util.ArrayList;

class Node {
    public int val;
    public ArrayList<Node> neighbors;

    public Node() {}

    public Node(int val, ArrayList<Node> neighbors) {
        this.val = val;
        this.neighbors = neighbors;
    }
}

public class CloneGraph {
    private HashMap<Node, Node> visited = new HashMap<>();

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

        // 如果节点已经被克隆，直接返回克隆节点
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // 创建新节点
        Node cloneNode = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneNode);

        // 递归克隆邻居节点并加入新节点的邻居中
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }

        return cloneNode;
    }
}

算法分析

• 时间复杂度：每个节点和每条边都只会被访问一次，因此时间复杂度为 O(N + E)，其中 N 是节点的数量，E 是边的数量。
• 空间复杂度：使用了哈希表存储节点映射关系，空间复杂度为 O(N)，其中 N 是节点的数量。

示例和测试

我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        CloneGraph solution = new CloneGraph();

        // 创建示例图
        Node node1 = new Node(1, new ArrayList<>());
        Node node2 = new Node(2, new ArrayList<>());
        Node node3 = new Node(3, new ArrayList<>());
        Node node4 = new Node(4, new ArrayList<>());
        node1.neighbors.add(node2);
        node1.neighbors.add(node4);
        node2.neighbors.add(node1);
        node2.neighbors.add(node3);
        node3.neighbors.add(node2);
        node3.neighbors.add(node4);
        node4.neighbors.add(node1);
        node4.neighbors.add(node3);

        Node clonedGraph = solution.cloneGraph(node1);
        // 在这里验证克隆图的正确性
    }
}

总结

克隆图问题是一个经典的图遍历问题，使用深度优先搜索可以较为简洁地解决。理解深度优先搜索的思想对于解决类似的图问题非常有帮助。通过构建一个映射关系的哈希表，我们能够在遍历的过程中完成节点的克隆，实现高效的图克隆算法。