Python怎么實現(xiàn)克隆圖

本篇內(nèi)容介紹了“Python怎么實現(xiàn)克隆圖”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

題目：

給定無向連通圖中一個節(jié)點的引用，返回該圖的深拷貝（克?。D中的每個節(jié)點都包含它的值 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}
解釋：
節(jié)點 1 的值是 1，它有兩個鄰居：節(jié)點 2 和 4 。
節(jié)點 2 的值是 2，它有兩個鄰居：節(jié)點 1 和 3 。
節(jié)點 3 的值是 3，它有兩個鄰居：節(jié)點 2 和 4 。
節(jié)點 4 的值是 4，它有兩個鄰居：節(jié)點 1 和 3 。

提示：

1. 節(jié)點數(shù)介于 1 到 100 之間。

2. 無向圖是一個簡單圖，這意味著圖中沒有重復(fù)的邊，也沒有自環(huán)。

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

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

解題思路：

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

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

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

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

Java：

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

Python3：

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

DFS：

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

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<>()));//每次都要新建節(jié)點并建立映射關(guān)系
 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] 時間復(fù)雜度都為1，但是在做算法題時肯定要用 dict[key] 這種方式。因為 get() 方法雖然效果一樣，但是反復(fù)調(diào)用函數(shù)造成的時間消耗非常高，python語言本來就慢，應(yīng)該養(yǎng)成盡可能優(yōu)化代碼的習(xí)慣

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