leetcode----133. Clone Graph

本文主要是介绍leetcode----133. Clone Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：

https://leetcode.com/problems/clone-graph/

大意：

给定一个图节点node，要求深度复制整个图。给定图的数据结构如下：

class Node {public int val;public List<Node> neighbors;public Node() {}public Node(int _val,List<Node> _neighbors) {val = _val;neighbors = _neighbors;}
};

例子：

思路：

深度复制，使用dfs以及一个map保存图节点值到图节点的映射。

若当前图节点以存在（即map中存在相应键为图节点值），则返回该图节点的引用；否则新建图节点。

代码：

// 每个节点的值都是不一样的？ 每个节点的值都不一样  不然怎么访问给定值的邻居？
class Solution {public Node cloneGraph(Node node) {Node n = new Node(node.val, new ArrayList<>());Map<Integer, Node> map = new HashMap<>();map.put(node.val, n);dfs(node, n, map);return n;}// 使用递归dfs构造cloneGraphpublic void dfs(Node nodeOld, Node nodeNew, Map<Integer, Node> map) {for (Node node : nodeOld.neighbors) {if (!map.containsKey(node.val)) {Node n = new Node(node.val, new ArrayList<>());map.put(node.val, n);nodeNew.neighbors.add(n);dfs(node, map.get(node.val), map);} else {nodeNew.neighbors.add(map.get(node.val));}}}
}

结果：

结论：

算法+数据结构=程序 

 

 

 

这篇关于leetcode----133. Clone Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---