演算法筆記：BFS 剝葉子法

這是什麼？

事先說明「BFS 剝葉子法」是我自己對它的暱稱，它嚴格來說並不能算是一種「演算法」，而是一種常見的設計技巧。

常見的對應名詞：「Topological Trimming（拓撲修剪）」、「Leaf Removal Algorithm（葉子移除演算法）」，如果在解題過程中看到這個提示，可以考慮使用這個……design patten？

其核心思想如下：

找到圖中的所有葉子（degree = 1 的節點）
逐層移除這些葉子，並更新剩餘圖的結構
持續進行，直到剩下的節點集合符合目標條件（例如：剩下圖的「中心點」）

資料結構

通常會需要兩個陣列，一個用於紀錄「每個點連到誰」，另一個用於紀錄「每個點連接了幾個」，需要區分有向圖和無向圖。

以 edges = [[1,0],[1,2],[1,3]] 為例，表示 Node 1 和 Node 0、2、3 有連接。

有向圖設計範例：

for (int i=0; i<edges.size(); i++) {
  graph[edges[i][0]].push_back(edges[i][1]);
  graph[edges[i][1]].push_back(edges[i][0]);
  degree[edges[i][0]]++;
  degree[edges[i][1]]++;
}
for (int i=0; i<degree.size(); i++) {
  if (degree[i] == 1) q.push(i);
}

無向圖設計範例：

for (int i=0; i<edges.size(); i++) {
  graph[edges[i][0]].push_back(edges[i][1]);
  degree[edges[i][0]]++;
}
for (int i=0; i<degree.size(); i++) {
  if (degree[i] == 1) q.push(i);
}

核心架構與實作

統計深度（degree）：計算每個節點連接的數量，degree = 1 的節點就是「葉子」
把所有葉子加入 queue 中
移除葉子：移除時，會使那些和葉子接在一起的節點 degree - 1，變成新的葉子
重複 step 2 與 step 3，直到節點數 ≤ 2

vector<int> result;
while (!q.empty()) {
  result.clear();
  int qSize = q.size();
  for (int i=0; i<qSize; i++) {
      int delNode = q.front(); q.pop();
      result.push_back(delNode);

      for (int j=0; j<graph[delNode].size(); j++) {
          degree[graph[delNode][j]]--;
          if (degree[graph[delNode][j]] == 1) q.push(graph[delNode][j]);
      }
  }
}