133. Clone Graph.md

133. Clone Graph

Cuz the description is too long, please refer to LeetCode URL

https://leetcode.com/problems/clone-graph/

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

代码

• BFS

  The main idea is to maintain an adjacency list in dict, visited[node].neighbors means the "node" holds all its neighbors in a list when we traverse the graph.

  Then, we need to avoid duplicate add, so everytime we choose to create the neighbor node if it is not visited, otherwise we just append this visited neighbor to visited[node].neighbors

  """
  # Definition for a Node.
  class Node:
      def __init__(self, val = 0, neighbors = None):
          self.val = val
          self.neighbors = neighbors if neighbors is not None else []
  """
  
  class Solution:
      def cloneGraph(self, node: 'Node') -> 'Node':
          if not node:
              return node
          visited = {}
          queue = deque([node])
          visited[node] = Node(node.val, [])
          
          # BFS
          while queue:
              n = queue.popleft()
              for nei in n.neighbors:
                  if nei not in visited:
                      visited[nei] = Node(nei.val, [])
                      queue.append(nei)
                  visited[n].neighbors.append(visited[nei])
          
          return visited[node]

• DFS