Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Solution: Create a queue, process node and it’s neighbors, create copies of nodes processed and create a reference in a dictionary between original and new nodes. Traverse dictionary to reestablish a relationship for new neighbors for copied nodes.

import UIKit

class Node {
    let title: String
    var neigbors: [Node]
    
    init(title: String) {
        self.title = title //assuming that title is a unique key
        self.neigbors = []
    }
    
    var description: String {
        var temp = ""
        for (node) in neigbors {
            temp += node.title + " "
        }
           return "Node: \(title) with Neigbors: \(temp)"
       }
}

// needs to conform to hashable in order to be inserted into the dictionary
extension Node: Hashable {
    // Equatable is needed for class in order to support Hashable
    static func == (lhs: Node, rhs: Node) -> Bool {
        return (lhs.title == rhs.title) && (lhs.neigbors == rhs.neigbors)
    }
    
  func hash(into hasher: inout Hasher) {
    hasher.combine(title)
   // hasher.combine(neigbors) // adding this will throw in the infinite loop
  }
}

func cloneGraph(root: Node) -> Node{
    var queue = [root]
    var cloneDict: [Node: Node] = [:]
   
    while queue.count > 0 {
        let cloneNode = Node(title: queue.first!.title + "-cloned")
        cloneDict.updateValue(cloneNode, forKey: queue.first!)
        
        //add only nodes that we haven't visited before
        for neigbor in queue.first!.neigbors {
            if ((cloneDict[neigbor] == nil)) {
                queue.append(neigbor)
            }
        }
        
        queue.remove(at: 0)
    }
    
    // reassign neigbors
    for (key, value) in cloneDict {
        for neigbor in key.neigbors {
            value.neigbors.append(cloneDict[neigbor]!)
        }
    }
    
    return cloneDict[root]!
}

func main() {
    let tempNodeA = Node(title: "A")
    let tempNodeB = Node(title: "B")
    let tempNodeC = Node(title: "C")
    let tempNodeD = Node(title: "D")
    
    tempNodeA.neigbors.append(tempNodeB)
    tempNodeA.neigbors.append(tempNodeD)
    tempNodeB.neigbors.append(tempNodeA)
    tempNodeB.neigbors.append(tempNodeC)
    tempNodeC.neigbors.append(tempNodeB)
    tempNodeC.neigbors.append(tempNodeD)
    tempNodeD.neigbors.append(tempNodeA)
    tempNodeD.neigbors.append(tempNodeC)
    
    print(cloneGraph(root: tempNodeA).description)
}

main()