Clone Graph

/*graph，用什么data structure来存graph，楼主说了下，用dictionary key存node 然后value 是set<node>。还问了这个东西叫啥。。楼主一时没想起来叫adjacency 啥的。然后他给了些example让实现一个graph class。 写完后clone graph，
克隆的基本思路就是， 存 original node - clone node 的map,  然后BFS 所有的original node, 一次链接
如果所有node的label都是没有dup的话， 可以用label来做map key， 就不需要实现hashable
*/


//BFS的实现方法。 注意不能重复进queue
func cloneGraph(_ node: Node) -> Node{
    // have to make node hashable inorder to put in map
    var map = [Node: Node]()    // orignode - clone node
    var queue = [Node]()
    let head = Node(node.label)
    map[node] = head

    while queue.count > 0 {
        let cur = queue.removeFirst()
        let clone = map[cur]! //只要进queue的肯定有克隆了
        var nextList = [Node]()
        for n in cur.neighbor {
            if let next = map[n]{
                nextList.append(next)
            }ellse {
                let next = Node(n.label)
                map[n] = next
                queue.append(n)
                nextList.append(next)
            }
        }
        clone.neighbor = nextList
    }
    return head
}

//DFS 的实现方法
var map2 = [Node: Node]()
func cloneGraphDFS(_ node: Node) -> Node{
    if let copy = map2[node] {
        return copy
    }
    let copy = Node(node.label)
    map2[node] = copy

    for n in node.neighbor {
        copy.neighbor.append(cloneGraphDFS(n))
    }
    return copy
}

var copy = cloneGraphDFS(n1)





//实现hashable是为了把node放到map里面
class Node : Hashable{
    var neighbor = [Node]()
    var label : String
    init(_ l: String) {
        label = l
    }
    static func == (ls: Node, rs: Node) -> Bool{
        return ls.label == rs.label
    }
    var hashValue: Int {
        return label.hashValue
    }
}