克隆图
题目形容：给你无向 连通 图中一个节点的援用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都蕴含它的值 val（int） 和其街坊的列表（list[Node]）。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：深度优先遍历
首先，如果以后节点为空，不必解决，间接返回。
否则，应用一个Map即visited来存储曾经解决过的图节点和相应的克隆节点，递归处理过程如下：
- 判断以后节点是否在visited中，如果在，则阐明曾经解决过了，则间接从visited中取出以后节点的克隆并返回。
- 否则，依据以后节点克隆出一个新的克隆节点，新克隆的节点的街坊节点初始化为空，而后将以后节点和新的克隆节点增加到visited中；
- 而后递归解决以后节点的街坊节点。
最初，返回以后节点的克隆节点。
解法二：广度优先遍历
同样的，首先，如果以后节点为空，不必解决，间接返回。
否则，也是须要初始化一个Map即visited来存储曾经解决过的图节点和相应的克隆节点，首先将以后节点和由以后节点克隆的节点增加到visited中，而后将以后节点增加到一个队列queue中，而后解决队列中的节点，晓得队列不为空，处理过程如下：
- 取出队列的头结点为curNode；
- 遍历解决curNode节点的街坊节点；
- 如果以后街坊节点不在visited，则将其和相应的克隆节点增加到visited中，并将其加到队列中；
- 而后将以后街坊节点的克隆节点增加到curNode的克隆节点的街坊节点列表中。
最初，返回初始节点的克隆节点。
注：图相干的算法还是理解的不多，得多学学。
import com.kaesar.leetcode.GraphNode;import java.util.*;public class LeetCode_133 { private static Map<GraphNode, GraphNode> visited = new HashMap<>(); /** * 深度优先遍历 * * @param node 以后节点 * @return */ public static GraphNode cloneGraph(GraphNode node) { if (node == null) { return node; } // 如果该节点曾经被拜访过了，则间接从哈希表中取出对应的克隆节点返回 if (visited.containsKey(node)) { return visited.get(node); } // 克隆以后节点 GraphNode cloneNode = new GraphNode(node.val, new ArrayList<>()); // 哈希表存储 visited.put(node, cloneNode); // 递归解决以后节点的街坊节点 for (GraphNode neighbor : node.neighbors) { cloneNode.neighbors.add(cloneGraph(neighbor)); } return cloneNode; } /** * 广度优先遍历 * * @param node 以后节点 * @return */ public static GraphNode cloneGraph2(GraphNode node) { if (node == null) { return node; } HashMap<GraphNode, GraphNode> visited = new HashMap<>(); Queue<GraphNode> queue = new LinkedList<>(); // 将以后节点增加到队列中 queue.add(node); // 克隆第一个节点并存储到哈希表中 visited.put(node, new GraphNode(node.val, new ArrayList<>())); // 广度优先遍历 while (!queue.isEmpty()) { // 取出队列的头节点 GraphNode curNode = queue.remove(); // 遍历以后节点的街坊节点 for (GraphNode neighbor : curNode.neighbors) { if (!visited.containsKey(neighbor)) { visited.put(neighbor, new GraphNode(neighbor.val, new ArrayList<>())); // 将街坊节点增加到队列中 queue.add(neighbor); } // 更新以后节点的街坊节点列表 visited.get(curNode).neighbors.add(visited.get(neighbor)); } } return visited.get(node); } public static void main(String[] args) { }}【每日寄语】 本人入手，饥寒交迫！