本篇內(nèi)容介紹了“Python怎么實(shí)現(xiàn)克隆圖”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
題目：
給定無向連通圖中一個(gè)節(jié)點(diǎn)的引用，返回該圖的深拷貝（克?。?。圖中的每個(gè)節(jié)點(diǎn)都包含它的值 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é)點(diǎn) 1 的值是 1，它有兩個(gè)鄰居：節(jié)點(diǎn) 2 和 4 。
節(jié)點(diǎn) 2 的值是 2，它有兩個(gè)鄰居：節(jié)點(diǎn) 1 和 3 。
節(jié)點(diǎn) 3 的值是 3，它有兩個(gè)鄰居：節(jié)點(diǎn) 2 和 4 。
節(jié)點(diǎn) 4 的值是 4，它有兩個(gè)鄰居：節(jié)點(diǎn) 1 和 3 。提示：
節(jié)點(diǎn)數(shù)介于 1 到 100 之間。
無向圖是一個(gè)簡(jiǎn)單圖，這意味著圖中沒有重復(fù)的邊，也沒有自環(huán)。
由于圖是無向的，如果節(jié)點(diǎn) p 是節(jié)點(diǎn) q 的鄰居，那么節(jié)點(diǎn) q 也必須是節(jié)點(diǎn) p 的鄰居。
必須將給定節(jié)點(diǎn)的拷貝作為對(duì)克隆圖的引用返回。
解題思路：
涉及到圖的遍歷無非就是DFS（深度優(yōu)先搜索）、BFS（廣度優(yōu)先搜索），可以先看前幾日的這篇文章：
BFS就需要借助隊(duì)列實(shí)現(xiàn)，DFS可以借助棧也可以直接用遞歸實(shí)現(xiàn)。就這道題而言直接用遞歸更好一些，無需開辟額外的數(shù)據(jù)結(jié)構(gòu)空間記錄節(jié)點(diǎn)。BFS、DFS寫法相對(duì)固定，建議花點(diǎn)時(shí)間一次性理解透，一勞永逸。
這道題思路很清晰，關(guān)鍵點(diǎn)是如何深拷貝隨機(jī)節(jié)點(diǎn)，可以參考鏈表的這篇文章：LeetCode 138：復(fù)制帶隨機(jī)指針的鏈表 Copy List with Random Pointer
鏈表是線性的，可以 復(fù)制節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)之后，很巧妙的完成深拷貝。顯然圖這樣的樹狀結(jié)構(gòu)無法用這種方法，只能借助數(shù)據(jù)結(jié)構(gòu)記錄已拷貝過的節(jié)點(diǎn)。這種需要映射新舊節(jié)點(diǎn)關(guān)系自然就是用散列表（字典）。
Java：
class Solution {
public Node cloneGraph(Node node) {
if (node == null) return node;
Queue queue = new LinkedList<>();//借助隊(duì)列實(shí)現(xiàn)BFS
Map map = new HashMap<>();//哈希映射
Node head = new Node(node.val, new ArrayList<>());//頭節(jié)點(diǎn)
map.put(node, head);//哈希映射原節(jié)點(diǎn)和新節(jié)點(diǎn)
queue.add(node);//原節(jié)點(diǎn)加入到隊(duì)列
while (!queue.isEmpty()) {//隊(duì)列不為空就重復(fù)循環(huán)
Node tmp = queue.poll();//彈出隊(duì)列頭節(jié)點(diǎn)
for (Node n : tmp.neighbors) {//遍歷鄰居節(jié)點(diǎn)
if (!map.containsKey(n)) {//字典的鍵不包含該節(jié)點(diǎn)時(shí)
map.put(n, new Node(n.val, new ArrayList<>()));//新建映射關(guān)系加入字典
queue.add(n);//加入隊(duì)列
}
map.get(tmp).neighbors.add(map.get(n));//加入鄰居節(jié)點(diǎn)
}
}
return head;
}
} Python3：
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node: return node
head = Node(node.val, [])#頭節(jié)點(diǎn)
map = {node: head}#初始化字典，并建立新舊節(jié)點(diǎn)的映射關(guān)系
queue = collections.deque()#隊(duì)列
queue.append(node)#原節(jié)點(diǎn)加入隊(duì)列
while queue:#隊(duì)列不為空
tmp = queue.popleft()#彈出隊(duì)列頭節(jié)點(diǎn)
for n in tmp.neighbors:#遍歷鄰居節(jié)點(diǎn)
if n in map.keys():#n節(jié)點(diǎn)存在于字典的鍵里時(shí)
map[tmp].neighbors.append(map[n])#直接加入到新節(jié)點(diǎn)的鄰居節(jié)點(diǎn)
else:
map[n] = Node(n.val, [])#新建節(jié)點(diǎn)并建立映射關(guān)系
map[tmp].neighbors.append(map[n])#由新建的映射關(guān)系取出節(jié)點(diǎn)并加入鄰居節(jié)點(diǎn)
queue.append(n)#該鄰居節(jié)點(diǎn)加入隊(duì)列
return headDFS：
遞歸完成的深度優(yōu)先搜索非常簡(jiǎn)潔，比較容易理解，唯一要注意的就是需要把字典定義在函數(shù)外。
Java：
class Solution {
Map map = new HashMap();
public Node cloneGraph(Node node) {
if (node == null) return node;
map.put(node, new Node(node.val, new ArrayList<>()));//每次都要新建節(jié)點(diǎn)并建立映射關(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時(shí)可以 dict().get(key) 也可以 dict[key] 時(shí)間復(fù)雜度都為1，但是在做算法題時(shí)肯定要用 dict[key] 這種方式。因?yàn)?get() 方法雖然效果一樣，但是反復(fù)調(diào)用函數(shù)造成的時(shí)間消耗非常高，python語言本來就慢，應(yīng)該養(yǎng)成盡可能優(yōu)化代碼的習(xí)慣
“Python怎么實(shí)現(xiàn)克隆圖”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
