本文共 2641 字，大约阅读时间需要 8 分钟。
https://oj.leetcode.com/problems/clone-graph/
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization: Nodes are labeled uniquely.
We use
# as a separator for each node, and
, as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph { 0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
- First node is labeled as
0. Connect node 0 to both nodes 1 and 2. - Second node is labeled as
1. Connect node 1 to node 2. - Third node is labeled as
2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / \ / \ 0 --- 2 / \ \_/
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList (); } * }; */ public UndirectedGraphNode cloneGraph(UndirectedGraphNode node)
这一题虽然说是图的克隆，但其实本质上就是无向图的全遍历。那么DFS和BFS在这里都是可以用的。就是用HashMap来进行路径记录避免循环路径。下面直接给出两段代码吧
DFS（实际上是一个bottom-up回收路径的过程）：
public UndirectedGraphNode DFShelper(UndirectedGraphNode node, HashMap visited){ if(visited.containsKey(node)) return visited.get(node); UndirectedGraphNode copy_node = new UndirectedGraphNode(node.label); visited.put(node, copy_node); for(UndirectedGraphNode n : node.neighbors){ copy_node.neighbors.add(DFShelper(n, visited)); } return copy_node; }
BFS：
public UndirectedGraphNode BFShelper(UndirectedGraphNode node){ Queue node_queue = new LinkedList (); HashMap visited = new HashMap (); UndirectedGraphNode res = new UndirectedGraphNode(node.label); visited.put(node, res); node_queue.add(node); while(!node_queue.isEmpty()){ UndirectedGraphNode cur_node = node_queue.poll(); UndirectedGraphNode copy_node = visited.get(cur_node); for(UndirectedGraphNode n : cur_node.neighbors){ UndirectedGraphNode copy_n = visited.containsKey(n) ? visited.get(n) : new UndirectedGraphNode(n.label); copy_node.neighbors.add(copy_n); if(!visited.containsKey(n))node_queue.add(n); visited.put(n, copy_n); } } return res; } 具体说一下哈希表的内容，键是原图的内容，值是拷贝的内容。所以每次DFS递归或者BFS循环的时候，总能在对应的点上取到对应的neighbors copy。BFS比较好理解，DFS实际上就是一个首先top-down遍历路径然后再bottom-up回收路径的一个做法。这在DFS上应该也是很常见的。
转载地址：http://egaxb.baihongyu.com/