PattySung

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 value (int) and a list (List[Node]) of its neighbors.

class Node { public int val; public List neighbors; } Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

-> 複製一個給定的 graph。可以分別用 BFS 跟 DFS 走訪每個 node 並複製，然後也將其連接的 nodes 複製並接上。

<解題> 深度優先搜索（DFS）


class Solution {
  private Map<Node, Node> map = new HashMap<>();

  public Node cloneGraph(Node node) {
    if (node == null)
      return null;

    if (map.containsKey(node))
      return map.get(node);

    Node clone = new Node(node.val);
    map.put(node, clone);

    for (Node neighbor : node.neighbors) {
      clone.neighbors.add(cloneGraph(neighbor));
    }

    return clone;
  }
}

Time: O(n) Space: O(n)

<解題> 廣度優先搜索（BFS）


class Solution {
    public Node cloneGraph(Node node) {
        if (node == null)
            return null;

        Queue<Node> queue = new LinkedList<>();
        Map<Node, Node> map = new HashMap<>();

        Node clone = new Node(node.val);
        queue.offer(node);
        map.put(node, clone);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            Node currClone = map.get(curr);

            for (Node neighbor : curr.neighbors) {
                if (!map.containsKey(neighbor)) {
                    Node neighborClone = new Node(neighbor.val);
                    map.put(neighbor, neighborClone);
                    queue.offer(neighbor);
                }
                currClone.neighbors.add(map.get(neighbor));
            }
        }

        return clone;
    }
}

Time: O(N + E)，其中N是節點數量，E是邊的數量 Space: O(N)

Leetcode-133. Clone Graph

<解題> 深度優先搜索（DFS）

<解題> 廣度優先搜索（BFS）