注意事項

  • 拜訪過的節點要記得標記，避免重複拜訪
  • DFS 沒啥好講的，故跳過

BFS（剝洋蔥）

int BFS(TreeNode* root, TreeNode* target) {
    queue<TreeNode*> q;
    unordered_set<TreeNode*> visited; // 避免重複拜訪

    int step = 0; // 紀錄步數
    q.emplace(root); // 將起點加入到 q 中
    visited.emplace(root);

    while (!q.empty()) {
        // 將當前 q 中的所有節點向四周擴散
        for (int k = q.size(); k > 0; --k) {
            const auto cur = q.front();
            q.pop();

            // 判斷是否達到終點
            if (cur == target) {
                return step;
            }

            // 將 cur 的相鄰節點加到 q 中
            for (const auto& v : cur.adj()) {
                // 如果相鄰節點未被拜訪過, 則將其加到 q 中
                if (visited.find(v) == visited.end()) {
                    q.emplace(v);
                    visited.emplace(v);
                }
            }
        }

        ++step; // 更新步數
    }

    return step;
}

Union Find

使用時機

  • 判斷兩個元素「是否在同一個 set」（e.g. 判斷 Graph 中是否有 cycle）

初始條件

  • 會用 parents、ranks 分別記錄每個 node 的 parent、以該點為 subtree root 的深度

  • 一開始每個 node 的 rank 都是 1

  • 一開始每個 node 都是自己一個 set, 其 parent 指向自己

Find

  • 查詢元素 i 的 root, e.g. 下圖中的 1、5 的 root 皆為 2, 因此 1、5 屬於同一個 set

    int find(const vector<int>& parents, int i){
        while (i != parents[i]) { // 若 i 不為 root
            i = parents[i]; // 則向上移動、查找
        }
        return i;
    }

Union

  • 將兩個不同的 set 合併成一個 set

    • 若深度不同, 則把深度低的 tree root 把深度高的 tree root 作為 parent

    • 若深度一樣, 則可以任意選擇一個 root 作為 parent, 只是作為 parent 的 node 之 rank 值會加一, 因為深度變了

      const int r1 = find(parents, n1); // root of n1
      const int r2 = find(parents, n2); // root of n2

      if (ranks[r1] > ranks[r2]) {
          parents[r2] = r1;
      } else if (ranks[r1] < ranks[r2]) {
          parents[r1] = r2;
      } else {
          parents[r2] = r1;
          ++ranks[r1]; // 作為 parent 的 node 之 rank 值會變加一, 因為深度變了
      }

Path Compression

  • 讓所有路徑上的點「直接」連到 root

  • 在 find(i) 時將 i 的父親設為祖父, 直到其父親為 root

    int find(vector<int>& parents, int i){
        while (i != parents[i]) { // 直到找到 root 才停止
            parents[i] = parents[parents[i]]; // 將父親設為祖父
            i = parents[i]; // 向上移動
        }
        return i;
    }

  • 時間複雜度：趨近 $O(1)$ 級別

經典例題