133. 克隆圖
題目來源：力扣（LeetCode）
https://leetcode-cn.com/problems/clone-graph
題目
給你無向 連通 圖中一個節(jié)點的引用，請你返回該圖的 深拷貝（克?。?。
圖中的每個節(jié)點都包含它的值 val（int） 和其鄰居的列表（list[Node]）。
class Node {
public int val;
public List<Node> neighbo rs;
}
測試用例格式：
簡單起見，每個節(jié)點的值都和它的索引相同。例如，第一個節(jié)點值為 1（val = 1），第二個節(jié)點值為 2（val = 2），以此類推。該圖在測試用例中使用鄰接列表表示。
鄰接列表 是用于表示有限圖的無序列表的集合。每個列表都描述了圖中節(jié)點的鄰居集。
給定節(jié)點將始終是圖中的第一個節(jié)點（值為 1）。你必須將 給定節(jié)點的拷貝 作為對克隆圖的引用返回。
示例 1：
輸入：adjList = [[2,4],[1,3],[2,4],[1,3]]
輸出：[[2,4],[1,3],[2,4],[1,3]]
解釋：
圖中有 4 個節(jié)點。
節(jié)點 1 的值是 1，它有兩個鄰居：節(jié)點 2 和 4 。
節(jié)點 2 的值是 2，它有兩個鄰居：節(jié)點 1 和 3 。
節(jié)點 3 的值是 3，它有兩個鄰居：節(jié)點 2 和 4 。
節(jié)點 4 的值是 4，它有兩個鄰居：節(jié)點 1 和 3 。
示例 2：
輸入：adjList = [[]]
輸出：[[]]
解釋：輸入包含一個空列表。該圖僅僅只有一個值為 1 的節(jié)點，它沒有任何鄰居。
示例 3：
輸入：adjList = []
輸出：[]
解釋：這個圖是空的，它不含任何節(jié)點。
示例 4：
輸入：adjList = [[2],[1]]
輸出：[[2],[1]]
提示：
- 節(jié)點數(shù)不超過 100 。
- 每個節(jié)點值 Node.val 都是唯一的，
1 <= Node.val <= 100。 - 無向圖是一個簡單圖，這意味著圖中沒有重復(fù)的邊，也沒有自環(huán)。
- 由于圖是無向的，如果節(jié)點 p 是節(jié)點 q 的鄰居，那么節(jié)點 q 也必須是節(jié)點 p 的鄰居。
- 圖是連通圖，你可以從給定節(jié)點訪問到所有節(jié)點。
解題思路
思路：DFS、BFS
在這道題中，題目要求的是圖的深拷貝。題目所述的圖的深拷貝，其實就是要構(gòu)建與原圖結(jié)構(gòu)，值均一樣的圖，但是 其中的節(jié)點不能再是原圖的引用。
題目開頭說了，給定的是一個節(jié)點的引用。但后面的提示也提及，圖是連通的，可以從給定的節(jié)點中去訪問所有節(jié)點。那么我們在進行訪問搜索的時候，完成圖的深拷貝。
深度優(yōu)先搜索（DFS）
這里先說下需要注意的地方，因為題目中明確說了，圖是無向圖，圖中的邊是無向邊。例如示例 4：
這里節(jié)點 1 和節(jié)點 2 存在無向邊，也就是說節(jié)點 1 可以到節(jié)點 2，而節(jié)點 2 也可以到 節(jié)點 1。所以我們遍歷搜索的時候要注意標(biāo)記，否則的話容易陷入死循環(huán)。
下面是具體算法：
- 前面說在遍歷訪問的時候進行標(biāo)記，這里我們借助哈希表來已經(jīng)被訪問和克隆的節(jié)點。其中鍵表示的是原圖的節(jié)點，而值表示的是克隆圖中對應(yīng)的節(jié)點；
- 從給定的節(jié)點開始向下搜索，如果節(jié)點存在于哈希表中，那么直接返回哈希表中的對應(yīng)的節(jié)點；
- 如果節(jié)點并沒有被標(biāo)記，那么創(chuàng)建克隆節(jié)點，存儲到哈希表中；
- 遞歸調(diào)用每個節(jié)點的鄰接點，將結(jié)果放到克隆鄰接點列表中。
具體的代碼見【代碼實現(xiàn) # 深度優(yōu)先搜索】
廣度優(yōu)先搜索（BFS）
使用廣度優(yōu)先搜索，這里同樣需要注意無向邊的問題。在這里，同樣使用哈希表來存儲已被訪問原圖的節(jié)點以及對應(yīng)克隆節(jié)點。下面是具體的算法：
- 使用哈希表來存儲已被訪問原圖的節(jié)點以及對應(yīng)克隆節(jié)點；
- 克隆給定的節(jié)點，存儲到哈希表中。同時借助輔助隊列，先將給定的節(jié)點放到隊列。
- 出隊，訪問該節(jié)點的所有鄰接點。如果節(jié)點不在哈希表中，那么克隆當(dāng)前節(jié)點的鄰接點存入哈希表中。同時將此鄰接點入隊，并將此鄰接點放到克隆圖中對應(yīng)節(jié)點的鄰接表中。
- 重復(fù)直至隊列為空，表明圖遍歷結(jié)束。
具體的代碼見【代碼實現(xiàn) # 廣度優(yōu)先搜索】
代碼實現(xiàn)
# 深度優(yōu)先搜索
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = []):
self.val = val
self.neighbors = neighbors
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
marked = {}
def dfs(node):
if not node:
return node
# 如果存在于哈希表中，直接返回哈希表存儲的值
if node in marked:
return marked[node]
# 不存在哈希表中，那么克隆節(jié)點，將其放入哈希表中
clone_node = Node(node.val, [])
marked[node] = clone_node
# 遍歷節(jié)點的鄰接點，相鄰接點放到鄰接列表中
for neighbor in node.neighbors:
clone_node.neighbors.append(dfs(neighbor))
return clone_node
return dfs(node)
# 廣度優(yōu)先搜索
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = []):
self.val = val
self.neighbors = neighbors
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
from collections import deque
marked = {}
def bfs(node):
if not node:
return node
# 克隆節(jié)點，放到哈希表中
clone_node = Node(node.val, [])
marked[node] = clone_node
# 先將給定的節(jié)點入隊
queue = deque()
queue.append(node)
# 出隊，開始遍歷
while queue:
cur_node = queue.popleft()
for neighbor in cur_node.neighbors:
# 如果鄰接點不在哈希表中，克隆鄰接點存入哈希表中，并將鄰接點入隊
if neighbor not in marked:
marked[neighbor] = Node(neighbor.val, [])
queue.append(neighbor)
# 更新當(dāng)前節(jié)點的鄰接列表，注意是克隆節(jié)點
marked[cur_node].neighbors.append(marked[neighbor])
return clone_node
return bfs(node)
實現(xiàn)結(jié)果
歡迎關(guān)注
公眾號 【書所集錄】
