题目

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
/ \
\_/


1. 根据解释，应该是有向图，而不是无向图。但不影响解题。
2. 这里每个节点的编号是唯一的。

深度优先dfs遍历，使用额外空间$O(n)$

代码

/**
* Definition for undirected graph.
* class UndirectedGraphNode {
*     int label;
*     List<UndirectedGraphNode> neighbors;
*     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) { return null; }
UndirectedGraphNode dummyOrigin = new UndirectedGraphNode(0);
UndirectedGraphNode dummyCopy = new UndirectedGraphNode(0);
dfs(dummyOrigin,dummyCopy,new HashMap<Integer,UndirectedGraphNode>());
return dummyCopy.neighbors.get(0);
}
public void dfs(UndirectedGraphNode origin, UndirectedGraphNode copy, Map<Integer,UndirectedGraphNode> existNodes) {
for (UndirectedGraphNode node : origin.neighbors) {
UndirectedGraphNode searchInExistNodes = existNodes.get(node.label);
if (searchInExistNodes != null) {
} else {
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
existNodes.put(node.label,newNode);
dfs(node,newNode,existNodes);
}
}
}
}


广度优先bfs遍历，使用额外空间$O(n)$

代码

/**
* Definition for undirected graph.
* class UndirectedGraphNode {
*     int label;
*     List<UndirectedGraphNode> neighbors;
*     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) { return null; }
UndirectedGraphNode dummyOrigin = new UndirectedGraphNode(0);
UndirectedGraphNode dummyCopy = new UndirectedGraphNode(0);
bfs(dummyOrigin,dummyCopy,new HashMap<Integer,UndirectedGraphNode>());
return dummyCopy.neighbors.get(0);
}
public void bfs(UndirectedGraphNode origin, UndirectedGraphNode copy, Map<Integer,UndirectedGraphNode> existNodes) {
Map<UndirectedGraphNode,UndirectedGraphNode> newNodes = new HashMap<>(); // 用一个Map预存接下来需要深入的新节点
for (UndirectedGraphNode node : origin.neighbors) {
UndirectedGraphNode searchInExistNodes = existNodes.get(node.label);
if (searchInExistNodes != null) {
} else {
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
newNodes.put(node,newNode);
existNodes.put(node.label,newNode);
}
}
for (Map.Entry<UndirectedGraphNode,UndirectedGraphNode> pair : newNodes.entrySet()) {
bfs(pair.getKey(),pair.getValue(),existNodes);
}
}
}