克隆一张无向图. 无向图的每个节点包含一个 label 和一个列表 neighbors. 保证每个节点的 label 互不相同. 你的程序需要返回一个经过深度拷贝的新图. 新图和原图具有同样的结构, 并且对新图的任何改动不会对原图造成任何影响. 你需要返回与给定节点具有相同 label 的那个节点.

说明

关于无向图的表示

在线评测地址

样例 1：

输入: {1,2,4#2,1,4#4,1,2} 输出:  {1,2,4#2,1,4#4,1,2} 解释: 1------2         |         |         |         |         4    

思路

从原图给定的点找到所有点 复制所有的点 复制所有的边

题解：

public class Solution {     /**      * @param node: A undirected graph node      * @return: A undirected graph node      */     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {         if (node == null) {             return node;         }          // use bfs algorithm to traverse the graph and get all nodes.         ArrayList<UndirectedGraphNode> nodes = getNodes(node);          // copy nodes, store the old->new mapping information in a hash map         HashMap<UndirectedGraphNode, UndirectedGraphNode> mapping = new HashMap<>();         for (UndirectedGraphNode n : nodes) {             mapping.put(n, new UndirectedGraphNode(n.label));         }          // copy neighbors(edges)         for (UndirectedGraphNode n : nodes) {             UndirectedGraphNode newNode = mapping.get(n);             for (UndirectedGraphNode neighbor : n.neighbors) {                 UndirectedGraphNode newNeighbor = mapping.get(neighbor);                 newNode.neighbors.add(newNeighbor);             }         }          return mapping.get(node);     }      private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {         Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();         HashSet<UndirectedGraphNode> set = new HashSet<>();          queue.offer(node);         set.add(node);         while (!queue.isEmpty()) {             UndirectedGraphNode head = queue.poll();             for (UndirectedGraphNode neighbor : head.neighbors) {                 if (!set.contains(neighbor)) {                     set.add(neighbor);                     queue.offer(neighbor);                 }             }         }          return new ArrayList<UndirectedGraphNode>(set);     } } 

更多题解参考

大佬有話說 (0)