題目敘述

我們必須透過已知的一個 graph 來建立一個一模一樣的 graph

但我們所回傳的 graph 不能是原本的 graph

解題思路

當遇到尋訪 graph 的題目

我們可以透過深度尋訪 / 廣度尋訪來完成

甚麼是深度尋訪?

想像你在走一個迷宮，正常我們都會朝一個方向找尋，直到走到沒路為止

深度尋訪就類似這一個概念

除此之外，他通常會透過一個類似 visited 的儲存方式去記說哪些點我們已經走過

# Pesuddo code for Depth First Search

visited = {} # It saves the node that we have already visited

def dfs(node):
    
    # if we traverse is not a node, return None
    
    # if we already visited the node, return
    
    # save the node in the visited
    
    # using recursive fun to call dfs() to visited the node.neighbors

甚麼是廣度尋訪?

廣度群訪與深度尋訪最大的不同在於，它每次只走一步

而這一步就是目前被尋訪點的鄰居們

通常我們會透過一個資料結構稱為 Queue 去儲存這些即將要被尋訪的點

這一個演算法會持續尋訪直到 Queue 當中沒有元素為止

def bfs(node):
    
    q = Queue() # create q to save the node for bfs
    
    visited = {} # It saves the node that we have already visited
    
    q.append([node]) # put the root or the first node that we need to visit into the queue
    
    while q: # the algorithm continues until the queue is empty
        for nei in node.neighbors:
            if nei not in visited:
                # append new node into queue
                # save the node in the visited and create cloned node for new node
            # save neighbors for cloned node

程式碼實作

以下演示深度尋訪的解題方式

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        
        if node == None:
            return None
        
        visited = {}
        
        def dfs(n):
            
            if n in visited:
                return visited[n]
            
            clone = Node(n.val)
            
            visited[n] = clone
            
            for nei in n.neighbors:
                clone.neighbors.append(dfs(nei))
                
            return clone
        
        return dfs(node)

以下演示廣度尋訪的解題方式

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        
        if node == None:
            return None
        
        q = deque([node])
        visited = {}
        visited[node] = Node(node.val)
        
        while q:
            cur = q.popleft()
            
            for nei in cur.neighbors:
                if nei not in visited:
                    q.append(nei)
                    visited[nei] = Node(nei.val)
                visited[cur].neighbors.append(visited[nei])
                
        return visited[node]
        
        

時間與空間複雜度分析

• 時間複雜度（Time Complexity）：$O(V + E)$

  • 通常 BFS 跟 DFS 會尋訪所有途中的節點跟邊，這裡的 V 代表 vertex (節點) 以及 E 代表 edge (邊)

• 空間複雜度（Space Complexity）：$O(V)$

  • 整個題目，五們主要是儲存 visited 也就是所尋訪過的節點