---
tags: 進階班
---

# DFS & BFS

## 前言

在暴力搜尋法中(就是無腦窮舉)，除了常見的幾種用 `for` 迴圈就可以達成的以外，

比較困難而且重要的就是 `DFS` 和 `BFS` 了。

## DFS (Depth First Search)

中文翻譯為：深度優先搜尋法

假設今天要處理：給定一數 $n$，求 $1$ ~ $n$ 的所有排列方法，

顯然靠 `for` 迴圈不太夠，因為你需要 $n$ 個 `for` 迴圈，而且 $n$ 是不固定的。

這時，我們可以靠遞迴來實現這個問題。

釐清我們需要什麼:

1. 對於每一格，$1$ ~ $n$ 都要有機會排進去 $\Rightarrow$ `for loop`

3. 我們需要把 $n$ 格都遍歷過 $\Rightarrow$ `dfs(cur + 1)`
4. 在一組排列中，不能有數字重複 $\Rightarrow$ `bool check[n]` 達成 $O(1)$ 判斷
5. 遞迴的 `return` 機制: `cur == n` (此時可以順便輸出目前排列)
6. 在 `return` 同時，因為會回到遞迴函式中的 `for` 迴圈並準備填入下一個數字，

因此要把 `check[i]` 還原，以利於後續 `i` 有機會再次被填入格子。

可以根據以上幾點寫出 `code`

#include<bits/stdc++.h>
using namespace std;
int arr[10], n; bool check[11];
void dfs(int cur) {
	if (cur == n) {
		for (int i = 0; i < n; i++) cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!check[i]) {
			check[i] = 1, arr[cur] = i;
			dfs(cur + 1);
			check[i] = 0, arr[cur] = 0;
		}
	}
}
int main() {
	while (cin >> n) dfs(0);
	return 0;
}

其實 `DFS` 的寫法有一定規則可循：

1. 先思考用什麼遞迴 (上述例子是數列第幾項)
2. `for loop` 視情況使用，有時候用不到
3. 遞迴時的 `check` 機制是什麼？

很多時候可以建陣列達成 $O(1)$，但有一些需要 $O(N),\; O(lgN)$判斷，

寫 `bool check()` 可能較美觀
4. 在遞迴時，判定可以繼續往下遞迴時，應該更新 `check` 再往下遞迴
5. 確定 `return` 條件，且 `return` 時，應把 `check` 還原

記起這些步驟，練個 $3$ 題左右，你就成為 `DFS, recursion` 大師了！

例題的小變化版：[a343: P(n, m) 的奧妙](http://203.64.191.163/ShowProblem?problemid=a343)

## BFS (Breadth First Search)

中文翻譯：廣度優先搜尋法

跟 `DFS` 的例題一樣：假設今天有一數 $n$，請你輸出所有 $1$ ~ $n$ 的排列方法。

雖然本題也是可以用 `DFS` 解，但是來聽聽別的思維：`BFS` 吧！

`BFS` 的概念是：先把第一格的所有可能記下來，

再把第二格填上去，

然後是第三格，以此類推直到結束。

最後再把所有解依序輸出即可。

在做 `BFS` 時，你需要：

1. 儲存單一種情況的容器 $\Rightarrow$ `vector`

2. 把所有 `vector` 儲存起來，而且需要存入及丟出：`deque`

3. 跟 `DFS` 一樣需要檢查那些數字已經被用過，不過這裡先用 $O(N)$ 檢查

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	while (cin >> n) {
		deque<vector<int>> dq = {{}};
		while (!dq.empty()) {
			vector<int> vec = dq.front(); dq.pop_front();
			if (vec.size() == n) {
				for (auto & i : vec) cout << i << ' ';
				cout << '\n';
                              break;
			}
			for (int i = 1; i <= n; i++) {
				bool flag = true;
				for (size_t j = 0; j < vec.size(); j++) {
					if (vec[j] == i) {flag = false; break;}
				}
				if (flag){
					vec.push_back(i);
					dq.push_back(vec);
					vec.pop_back();
				}
			}
		}
	}
	return 0;
}

顯然這題不是一個好的 `BFS` 例題 (空間、時間複雜度都堪憂)

真正會用 `BFS` 來解的是走迷宮最短路徑之類的題目

(從起點開始往外走，最先碰到終點的步數即最短路徑)

例如：[a337: Maze Runner](http://203.64.191.163/ShowProblem?problemid=a337)

## DFS & BFS 重要技巧：剪枝

假設今天有一個題目：給定一字串 $s$，輸出 $s$ 的所有子序列。

可能可以用 `DFS` 無腦解：

string str; bool check[10];
void dfs(string s, int idx) {
	cout << s << '\n';
	for (size_t i = idx; i < str.size(); i++) {
		if (!check[i]) {
			s += str[i], check[i] = 1;
			dfs(s, i + 1);
			s.erase(s.end() - 1), check[i] = 0;
		}
	}
}
int main() {
	while (cin >> str) {
		dfs("", 0);
	}
	return 0;
}

但是，假設今天輸入的字串有重複字元呢？

~~把子序列排序後再用 `unique` 篩出唯一字串~~

如果今天的字串是 `AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`，那這樣子序列數量超過 $10^9$，顯然不太行。

這時要使用「剪枝」技術，讓產生的字串不重複。

小提示：在子序列 $str$ 中，若 `str.pos(i) < str.pos(j)`，則 `s.pos(i) < s.pos(j)`

1. 先把整個字串先 `sort` 過一遍，但是要記下字元原位置

2. 如果不想處理到重複字串，則 `dfs` 時 `s += str[i]` 之 `str[i]` 不可以重複
$\Rightarrow$ 可以設一個 `char pre` 記錄前一個字元取了什麼 (字串已經 `sort` 過了，因此重複字元相鄰)
3. 要判斷 `str.pos[s[s.size() - 1]] < str.pos[i]`
4. 第 2. 點 和 第 3. 點 就是這個剪枝 `DFS` 的 `check` 機制

string str;
vector<pair<char, int>> v(11);
void dfs(string s, int pre_pos) {
	cout << s << '\n';
	char pre_ch = 0; //NULL
	for (size_t i = 1; i <= str.size(); i++) {
		if (pre_pos < v[i].s && pre_ch != v[i].f) {
			s += v[i].f, pre_ch = v[i].f;
			dfs(s, v[i].s);
			s.erase(s.end() - 1);
		}
	}
}
int main() {
	while (cin >> str) {
		v[0].f = '#', v[0].s = -1;
		for (size_t i = 1; i <= str.size(); i++) {
			v[i].f = str[i - 1], v[i].s = i;
		}
		sort(v.begin() + 1, v.begin() + str.size() + 1);
		dfs("", -1);
	}
	return 0;
}

這題的 `BFS` 也是同樣道理，如果直接處理 `BFS`，空間一樣會爆。

那麼，`BFS` 剪枝方法是？

其實和 `DFS` 差不多，一樣是判斷 `pre_ch != i.ch && pre_pos < i.pos`

附上有 `struct` 的寫法或許可以看得比較懂(？

(變數名稱不是 `first` 和 `second`)

struct wd {
	char c; int idx;
	bool operator<(const wd& w) const{return c == w.c ? c < w.c : idx < w.idx;}
};
struct ans {string s; wd w;};
int main() {
	vector<wd> str(11);
	string s;
	while (cin >> s) {
		const int len = int(s.length());
		for (int i = 0; i < len; i++) str[i].c = s[i], str[i].idx = i;
		sort(str.begin(), str.begin() + len);
		deque<ans> dq{{"", {0, -1}}};
		while (!dq.empty()) {
			ans tmp = dq.front(); dq.pop_front();
			cout << tmp.s << '\n';
			char pre = 0;
			for (int i = 0; i < len; i++) {
				if (pre == str[i].c) continue;
				else if (str[i].idx > tmp.w.idx) {
					dq.push_back({tmp.s + str[i].c, str[i]});
					pre = str[i].c;
				}
			}
		}
	}
	return 0;
}