Python怎么實現克隆圖

本篇內容介紹了“Python怎么實現克隆圖”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

題目：

給定無向連通圖中一個節點的引用，返回該圖的深拷貝（克隆）。圖中的每個節點都包含它的值 val（Int） 和其鄰居的列表（list[Node]）。

示例：

輸入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
解釋：
節點 1 的值是 1，它有兩個鄰居：節點 2 和 4 。
節點 2 的值是 2，它有兩個鄰居：節點 1 和 3 。
節點 3 的值是 3，它有兩個鄰居：節點 2 和 4 。
節點 4 的值是 4，它有兩個鄰居：節點 1 和 3 。

提示：

1. 節點數介于 1 到 100 之間。

2. 無向圖是一個簡單圖，這意味著圖中沒有重復的邊，也沒有自環。

3. 由于圖是無向的，如果節點 p 是節點 q 的鄰居，那么節點 q 也必須是節點 p 的鄰居。

4. 必須將給定節點的拷貝作為對克隆圖的引用返回。

解題思路：

涉及到圖的遍歷無非就是DFS（深度優先搜索）、BFS（廣度優先搜索），可以先看前幾日的這篇文章：

BFS就需要借助隊列實現，DFS可以借助棧也可以直接用遞歸實現。就這道題而言直接用遞歸更好一些，無需開辟額外的數據結構空間記錄節點。BFS、DFS寫法相對固定，建議花點時間一次性理解透，一勞永逸。

這道題思路很清晰，關鍵點是如何深拷貝隨機節點，可以參考鏈表的這篇文章：LeetCode 138：復制帶隨機指針的鏈表 Copy List with Random Pointer

鏈表是線性的，可以 復制節點到每個節點之后，很巧妙的完成深拷貝。顯然圖這樣的樹狀結構無法用這種方法，只能借助數據結構記錄已拷貝過的節點。這種需要映射新舊節點關系自然就是用散列表（字典）。

Java：

class Solution {
 public Node cloneGraph(Node node) {
 if (node == null) return node;
 Queue<Node> queue = new LinkedList<>();//借助隊列實現BFS
 Map<Node, Node> map = new HashMap<>();//哈希映射
 Node head = new Node(node.val, new ArrayList<>());//頭節點
 map.put(node, head);//哈希映射原節點和新節點
 queue.add(node);//原節點加入到隊列
 while (!queue.isEmpty()) {//隊列不為空就重復循環
 Node tmp = queue.poll();//彈出隊列頭節點
 for (Node n : tmp.neighbors) {//遍歷鄰居節點
 if (!map.containsKey(n)) {//字典的鍵不包含該節點時
 map.put(n, new Node(n.val, new ArrayList<>()));//新建映射關系加入字典
 queue.add(n);//加入隊列
 }
 map.get(tmp).neighbors.add(map.get(n));//加入鄰居節點
 }
 }
 return head;
 }
}

Python3：

class Solution:
 def cloneGraph(self, node: 'Node') -> 'Node':
 if not node: return node
 head = Node(node.val, [])#頭節點
 map = {node: head}#初始化字典，并建立新舊節點的映射關系
 queue = collections.deque()#隊列
 queue.append(node)#原節點加入隊列
 while queue:#隊列不為空
 tmp = queue.popleft()#彈出隊列頭節點
 for n in tmp.neighbors:#遍歷鄰居節點
 if n in map.keys():#n節點存在于字典的鍵里時
 map[tmp].neighbors.append(map[n])#直接加入到新節點的鄰居節點
 else:
 map[n] = Node(n.val, [])#新建節點并建立映射關系
 map[tmp].neighbors.append(map[n])#由新建的映射關系取出節點并加入鄰居節點
 queue.append(n)#該鄰居節點加入隊列
 return head

DFS：

遞歸完成的深度優先搜索非常簡潔，比較容易理解，唯一要注意的就是需要把字典定義在函數外。

Java：

class Solution {
 Map<Node, Node> map = new HashMap();
 public Node cloneGraph(Node node) {
 if (node == null) return node;
 map.put(node, new Node(node.val, new ArrayList<>()));//每次都要新建節點并建立映射關系
 for (Node n : node.neighbors) {
 if (map.containsKey(n)) map.get(node).neighbors.add(map.get(n));
 else map.get(node).neighbors.add(cloneGraph(n));
 }
 return map.get(node);
 }
}

Python3：

class Solution:
 map = dict()
 def cloneGraph(self, node: 'Node') -> 'Node':
 if not node: return node
 self.map[node] = Node(node.val, [])
 for n in node.neighbors:
 if n in self.map.keys():
 self.map[node].neighbors.append(self.map[n])
 else:
 self.map[node].neighbors.append(self.cloneGraph(n))
 return self.map[node]

注意：

python中的字典取values時可以 dict().get(key) 也可以 dict[key] 時間復雜度都為1，但是在做算法題時肯定要用 dict[key] 這種方式。因為 get() 方法雖然效果一樣，但是反復調用函數造成的時間消耗非常高，python語言本來就慢，應該養成盡可能優化代碼的習慣

“Python怎么實現克隆圖”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！