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

Solution: BFS遍历图 用Hash表存储Original Node-》 Copy Node 映射

O(n) time complexity, O(n) space

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return null; } Queue<UndirectedGraphNode> queue = new LinkedList<>(); Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>(); queue.offer(node); UndirectedGraphNode copyRoot = new UndirectedGraphNode(node.label); map.put(node, copyRoot); while (!queue.isEmpty()) { int count = queue.size(); for (int i = 0; i < count; i++) { UndirectedGraphNode curr = queue.poll(); for (UndirectedGraphNode neighbor : curr.neighbors) { if (!map.containsKey(neighbor)) { queue.offer(neighbor); UndirectedGraphNode currCopy = new UndirectedGraphNode(neighbor.label); map.put(neighbor, currCopy); } } } } for (UndirectedGraphNode originalNode : map.keySet()) { for (UndirectedGraphNode neighbor : originalNode.neighbors) { map.get(originalNode).neighbors.add(map.get(neighbor)); } } return map.get(node); }