No. 133 - Clone Graph
====


---

## [LeetCode 133 -- Clone Graph](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 value (`int`) and a list (`List[Node]`) of its neighbors.

class Node {
    public int val;
    public List<Node> 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 複製並接上。

### 解法 1. Breadth First Search

完整程式碼如下:

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    Node* cloneGraph(Node* node) {
      if (!node)
        return NULL;
      unordered_map<Node*, Node*> visit;
      queue<Node*> q;
      q.push(node);
      visit[node] = new Node(node->val);
      
      while (!q.empty()) {
        Node *cur = q.front();
        q.pop();
        
        for (Node* neighbor: cur->neighbors){
          if (visit.find(neighbor) == visit.end()) {
            visit[neighbor] = new Node(neighbor->val);
            q.push(neighbor);
          }
          visit[cur]->neighbors.push_back(visit[neighbor]);
        }
      }
      return visit[node];
    }
};

當我們每走訪一個 node，因為是 BFS，所以我們在每次走訪一個 node 就可以先把該 node 複製並且把它相鄰的 node 也都複製並且接上 (第 36-42 行)。

但因為每個相鄰 node 也都可能會是其它 node 的相鄰的 node 所以可能早就複製過了，所以我們會需要一個紀錄每個 node 有沒有被走訪的 map `unordered_map<Node*, Node*> visit`，這個 map 的第一個指標是存原本的 node，第二個指標是存複製過後的 node。

我們每次要複製走訪 node 的相鄰 node 前只要查這個 map 看有沒有存在該 node 的指標就知道有沒有被複製過 (第 37-39 行)，而只有還沒複製過的相鄰 node 會需要之後再走訪，因為還沒複製過也就代表這個 node 還沒有被走訪，因此它的複製的 node 也還沒有接上其他相鄰的複製的 nodes。

### 解法 2. Depth First Search

完整程式碼如下:

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    Node* dfs(Node *node, unordered_map<Node*, Node*> &visit) {
      Node *copy = new Node(node->val);
      visit[node] = copy;
      for (int i=0; i<node->neighbors.size(); ++i) {
        Node *neighbor = node->neighbors[i];
        if (visit.find(neighbor) == visit.end()) {
          Node *copy_neighbor = dfs(neighbor, visit);
          copy->neighbors.push_back(copy_neighbor);
        }
        else {
          copy->neighbors.push_back(visit[neighbor]);
        }
      }
      return visit[node];
    }
    Node* cloneGraph(Node* node) {
      if (!node)
        return node;
      unordered_map<Node*, Node*> visit;
      return dfs(node, visit);
    }
};

相較於 BFS，DFS 不會一次就把走訪的 node 的相鄰 nodes 都複製，而是選擇其中一個相鄰的 node 複製然後再以該 node 繼續往下走訪並遞迴的做此動作。

所以每次複製一個 node DFS 的做法並不會一次就接上該 node 的相鄰 node 的複製，而是一次只接一個複製的相鄰 node，而此複製的相鄰 node 就是下一次要走訪的 node。

跟 BFS 一樣的是每當要複製正在走訪的 node 的相鄰 node 前，我們都要去檢查 `visit` map，看看此 node 是不是已經有在走訪其他 node 時就已經複製過了。如果已經複製過了就不需要複製並且走訪，只需要把它已經複製的 node 接上正在走訪的 node 即可。

### 複雜度分析

這類需要做 graph search 一定會走訪所有的 nodes 且至少也會走訪每一條邊一遍，因為要判斷是否要走訪相鄰的 nodes，所以需要的時間複雜度為 $O(V+E)$，其中 $V$ 為 nodes 數量，$E$ 為邊的數量。

空間複雜度上，BFS 的 queue 最多會需要存 $V-1$ 的 nodes，而 DFS 最多也需要做 $V-1$ recursive，所以複雜度都是 $O(V)$。