Clone Graph

描述不写了，这道题实际上就是copy random linked list的图版本，不过跟那道题不同的是，因为图不是线性数据结构，这里就没办法再用那种空间复杂度O(1)的算法了，只能老实用哈希表来做，这里最直觉的方法就是用BFS和哈希表在遍历图的过程中建立新节点然后利用哈希表映射，然后再遍历这个哈希表把每个点的邻居也创建出来，值得一提的是在BFS时的查重放在外层循环标注和内层循环标注都可行，但是一般来讲查重都是放在内层循环才能避免错误，这里也能放在外层的原因是因为每次一个点出来的时候我们要进行的操作只是在哈希表里面建立一个对应的镜像结点而已，所以即使重复操作也无所谓，因为都是一样的，下面是这种逻辑的代码

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        if not node:
            return None

        hst = {}
        ref = {}
        stack = [node]
        ref[node] = 1

        while stack:
            point = stack.pop()
            hst[point] = UndirectedGraphNode(point.label)
            for neighbor in point.neighbors:
                if neighbor in ref:
                    continue
                ref[neighbor] = 1
                stack.append(neighbor)

        for point, new_node in hst.items():
            for neighbor in point.neighbors:
                new_node.neighbors.append(hst[neighbor])

        return hst[node]

另外还有用递归DFS和非递归DFS的方法做这道题，但是觉得没有BFS这么直觉，暂时也没这么写，下面是稍微更改了一下用set来完成dict的任务

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        if not node:
            return node

        queue = [node]
        checker = set()
        relation = {}

        while queue:
            curNode = queue.pop()
            checker.add(curNode)
            relation[curNode] = UndirectedGraphNode(curNode.label)
            for curNeigh in curNode.neighbors:
                if curNeigh not in checker:
                    checker.add(curNeigh)
                    queue.append(curNeigh)

        for curNode in checker:
            for curNeigh in curNode.neighbors:
                relation[curNode].neighbors.append(relation[curNeigh])

        return relation[node]