无向连通图节点深拷贝实现与示例

本题是一道关于图算法的编程问题，要求解决的是在无向连通图中，给定一个节点（通常表示为第一个节点，值为1）的引用，创建一个该图的深拷贝或克隆。题目涉及的是一种典型的图数据结构，即邻接列表（Adjacency List），它用于表示图中节点间的连接关系，每个节点都有一个值和指向其他节点的邻居列表。 克隆图意味着我们需要构建一个新的图，其中包含原图中所有节点及其邻居关系，但又是一个独立的副本，不会影响原图的结构。在实现时，可以遍历原图的每个节点，创建新的节点并添加到新图中，同时复制它们的值和邻居。对于邻居，我们需要对原图中相邻的节点进行递归处理，确保所有相连的节点都被添加到新图中，并保持它们之间的链接。 以下是一个可能的解决方案： 1. 首先，定义一个Node类，与给定的定义一致，包括一个整数值val和一个Node类型的邻居列表neighbors。 ```java class Node { public int val; public List<Node> neighbors; // 初始化方法，省略 } ``` 2. 创建一个辅助函数`cloneNode(node: Node) -> Node`，用于深度复制一个节点，包括其值和邻居列表。 ```java Node cloneNode(Node node) { Node newNode = new Node(); newNode.val = node.val; newNode.neighbors = new ArrayList<>(); for (Node neighbor : node.neighbors) { newNode.neighbors.add(cloneNode(neighbor)); } return newNode; } ``` 3. 主函数`cloneGraph(adjList: List<List<Node>>) -> List<Node>`，接受邻接列表作为输入，返回克隆后的图的引用。 ```java List<Node> cloneGraph(List<List<Node>> adjList) { if (adjList.isEmpty()) { return Collections.emptyList(); } Node firstNode = adjList.get(0).get(0); // 假设给定节点是第一个 Node clonedFirstNode = cloneNode(firstNode); // 使用栈或队列进行广度优先搜索(BFS)或深度优先搜索(DFS)，遍历并克隆其他节点 // 使用clonedFirstNode作为起点，将新邻居添加到clonedFirstNode.neighbors // 对于所有子节点，递归调用cloneGraph，将结果添加到对应的邻居列表中 return Collections.singletonList(clonedFirstNode); // 返回克隆后的第一个节点作为整个图的引用 } ``` 测试用例表明，此方法适用于各种情况，包括空图、单节点图、多边形图以及具有多个节点和连接的复杂图。需要注意的是，虽然题目提示节点数不超过100，但在实际应用中，这种方法可以扩展到更大的规模，只要内存足够处理节点和邻接列表的数量。