Clone Graph

题目

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.

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#.

1. First node is labeled as0. Connect node0to both nodes1and2.
2. Second node is labeled as1. Connect node1to node2.
3. Third node is labeled as2. Connect node2to node2(itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

思路分析

这道题是clone一个graph，基本思路是用BFS，把每一个old vertex以及old vertex的neighbors都放在queue中，每一次pop queue的first element。同时要用dictionary存放old vertex跟cloned vertex之间的映射。这个映射可以判断一个vertex是不是已经被clone，如果已经被clone，那么就可以直接使用clone的vertex

• queue：存放每一个old vertex
• dictionary：存放old vertex跟cloned vertex之间的映射

# 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
        nodeCopy = UndirectedGraphNode(node.label)
        queue = [node]              <<<<< queue to store the old vertex
        hmap = {node: nodeCopy}     <<<<< mapping between old vertex and cloned vertex
        while queue:
            node = queue.pop(0)
            neighbors = node.neighbors
            for neighbor in neighbors:
                if not neighbor in hmap:
                    neighborCopy = UndirectedGraphNode(neighbor.label)
                    hmap[neighbor] = neighborCopy
                    hmap[node].neighbors.append(neighborCopy)
                    queue.append(neighbor)
                else: 
                    hmap[node].neighbors.append(hmap[neighbor])
        return nodeCopy