Crack LeetCode 之 133. Clone Graph

本文主要是介绍Crack LeetCode 之 133. Clone Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode link: https://leetcode.com/problems/clone-graph/

本题要求克隆一个图。这里需要的注意的是，每个节点的相邻节点可能有重复，所以需要一个map检查重复节点。另外，本题还有两个解法：深度优先遍历和广度优先遍历。可以参考https://blog.csdn.net/linhuanmars/article/details/22715747，从这个链接我们可以看到广度优先和深度优先的遍历区别在于，前者用队列做数据结构，后者用栈做数据结构。我比较喜欢本体的递归实现，很简洁。

以下是C++代码，空间复杂度是O(n)，时间复杂度也是O(n)。

class Solution {map<UndirectedGraphNode *, UndirectedGraphNode *> m_map;public:UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {if (node == NULL)return NULL;UndirectedGraphNode * result = new UndirectedGraphNode(node->label);m_map[node] = result;for (int i=0; i<node->neighbors.size(); ++i)result->neighbors.push_back( m_map[node->neighbors[i]]? m_map[node->neighbors[i]]: cloneGraph(node->neighbors[i]) );return result;}
};

class Solution:def __init__(self):self.m_dictionary = {}def cloneGraph(self, node):if node is None:return Noneroot = UndirectedGraphNode(node.label)self.m_dictionary[node] = rootfor item in range( len(node.neighbors) ):if self.m_dictionary.get(node.neighbors[item]) is not None:root.neighbors.append( self.m_dictionary[node.neighbors[item]] )else:root.neighbors.append( self.cloneGraph( node.neighbors[item] ) )return root

 

这篇关于Crack LeetCode 之 133. Clone Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---