本文共 1524 字，大约阅读时间需要 5 分钟。

类似于二叉树的三种遍历，我们可以基于遍历的模板做很多额外的事情，图的两种遍历，深度和广度模板同样也可以做很多额外的事情，这里举例利用深度优先遍历的模板来进行复制，深度优先中，我们先访问第一个结点，接着访问第一个邻接点，再访问邻节点的邻节点。。。。

class Solution:    # @param node, a undirected graph node    # @return a undirected graph node    def cloneGraph(self, node):        if None == node: return None        nodeMap = {}        return self.cloneNode(node, nodeMap)            def cloneNode(self, node, nodeMap):        if None == node:            return None        #访问当前点，这里不是简单的print，而是复制，若已经复制，则返回副本        if nodeMap.has_key(node):            return nodeMap[node]        #若没有副本，则复制一份，同样处理其邻接点        else:            clone = UndirectedGraphNode(node.label)            nodeMap[node] = clone            #访问其邻居节点            for neighbor in node.neighbors:                clone.neighbors.append(self.cloneNode(neighbor, nodeMap))        return clone

Copy List with Random Pointer

class Solution:    # @param head, a RandomListNode    # @return a RandomListNode    def copyRandomList(self, head):        if None == head: return None        nodeMap = {}        return self.copyListNode(head, nodeMap)            def copyListNode(self, node, nodeMap):        if None == node: return None        if nodeMap.has_key(node):            return nodeMap[node]        else:             cpNode = RandomListNode(node.label)            nodeMap[node] = cpNode            cpNode.next = self.copyListNode(node.next, nodeMap)            cpNode.random = self.copyListNode(node.random, nodeMap)        return cpNode

转载地址：http://oumji.baihongyu.com/