```
/*
Solution1. DFS. time = O(n) - each node is cloned once; space = O(n)
Steps:
1. clone each node
2. clone each node's neighbors
Keep the above steps recursively
{0,1,2#1,2#2,2}: #nodeA, NodeA.neighbor0, NodeA.neighbor1,.. #NodeB, NodeB.neighbor0, NodeB.neighbor01
0: neighbors = 1, 2
1: neighbors = 2 - because #1, 2 (1's neighbor is 2)
2: neighbors = 2 - self-cycle
1
/ \
0 -- 2
/_\
*/
func cloneGraph1(_ node: UndirectedGraphNode) -> UndirectedGraphNode {
var map = [UndirectedGraphNode: UndirectedGraphNode]() // map: [original: cloned]
return DFS(node, &map)
}
/// - Returns: the cloned node
private func DFS(_ original: UndirectedGraphNode, _ map: inout [UndirectedGraphNode: UndirectedGraphNode]) -> UndirectedGraphNode{
if map.keys.contains(original) {// Visited: Use hashMap to avoid duplicates: Node original was already cloned, return its clone from map hashMap.
return map[original]!
}
// Clone node
let cloned = UndirectedGraphNode(original.label)
map[original] = cloned
cloned.neighbors = [UndirectedGraphNode]()
// Clone neighbors
for neighbor in original.neighbors {
cloned.neighbors.append(DFS(neighbor, &map))
}
return cloned
}
/*Solution2. BFS - O(n) runtime; O(n) space
Steps:
1. Clone all nodes
2. Add the cloned nodes' neighbors
*/
func cloneGraph(_ node: UndirectedGraphNode) -> UndirectedGraphNode {
var map = [UndirectedGraphNode: UndirectedGraphNode]() // map: [original: cloned]
var queue = Queue<UndirectedGraphNode>()
queue.offer(node)
while !queue.isEmpty() {// BFS (queue): Clone nodes
let count = queue.size
for _ in 0 ..< count {
let original = queue.poll()!
if map.keys.contains(original) {// Visited: ignore the node to avoid duplicates
continue
}
// Clone node
let cloned = UndirectedGraphNode(original.label)
map[original] = cloned
for neighbor in original.neighbors {
queue.offer(neighbor)
}
}
}
// Clone neighbors: add cloned neighbors to cloned node
for original in map.keys {
let cloned = map[original]!
cloned.neighbors = original.neighbors.map{ map[$0]! }// get cloned neighbors in map
}
return map[node]!
}
```