本文為Leetcode學(xué)習(xí)筆記
隊列和廣度優(yōu)先搜索（BFS）
廣度優(yōu)先搜索（BFS）的一個常見應(yīng)用是找出從根結(jié)點到目標(biāo)結(jié)點的最短路徑。在本文中，我們提供了一個示例來解釋在 BFS 算法中是如何逐步應(yīng)用隊列的。
1. 結(jié)點的處理順序是什么？
在第一輪中，我們處理根結(jié)點。在第二輪中，我們處理根結(jié)點旁邊的結(jié)點；在第三輪中，我們處理距根結(jié)點兩步的結(jié)點；等等等等。
與樹的層序遍歷類似，越是接近根結(jié)點的結(jié)點將越早地遍歷。
如果在第 k 輪中將結(jié)點 X 添加到隊列中，則根結(jié)點與 X 之間的最短路徑的長度恰好是 k。也就是說，第一次找到目標(biāo)結(jié)點時，你已經(jīng)處于最短路徑中。
2. 隊列的入隊和出隊順序是什么？
我們首先將根結(jié)點排入隊列。然后在每一輪中，我們逐個處理已經(jīng)在隊列中的結(jié)點，并將所有鄰居添加到隊列中。值得注意的是，新添加的節(jié)點不會立即遍歷，而是在下一輪中處理。
結(jié)點的處理順序與它們添加到隊列的順序是完全相同的順序，即先進先出（FIFO）。這就是我們在 BFS 中使用隊列的原因。
在特定問題中執(zhí)行 BFS 之前確定結(jié)點和邊緣非常重要。通常，結(jié)點將是實際結(jié)點或是狀態(tài)，而邊緣將是實際邊緣或可能的轉(zhuǎn)換。
模板 I
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
- 如代碼所示，在每一輪中，隊列中的結(jié)點是等待處理的結(jié)點。
- 在每個更外一層的 while 循環(huán)之后，我們距離根結(jié)點更遠(yuǎn)一步。變量 step 指示從根結(jié)點到我們正在訪問的當(dāng)前結(jié)點的距離。
模板II
有時，確保我們永遠(yuǎn)不會訪問一個結(jié)點兩次很重要。否則，我們可能陷入無限循環(huán)。如果是這樣，我們可以在上面的代碼中添加一個哈希集來解決這個問題。這是修改后的偽代碼：
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> used; // store all the used nodes
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to used;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to used;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
有兩種情況你不需要使用哈希集：
- 你完全確定沒有循環(huán)，例如，在樹遍歷中；
- 你確實希望多次將結(jié)點添加到隊列中。
棧和深度優(yōu)先搜索（DFS）
與 BFS 類似，深度優(yōu)先搜索（DFS）也可用于查找從根結(jié)點到目標(biāo)結(jié)點的路徑。在本文中，我們提供了示例來解釋 DFS 是如何工作的以及棧是如何逐步幫助 DFS 工作的。
圖
1. 結(jié)點的處理順序是什么？
在上面的例子中，我們從根結(jié)點 A 開始。首先，我們選擇結(jié)點 B 的路徑，并進行回溯，直到我們到達(dá)結(jié)點 E，我們無法更進一步深入。然后我們回溯到 A 并選擇第二條路徑到結(jié)點 C 。從 C 開始，我們嘗試第一條路徑到 E 但是 E 已被訪問過。所以我們回到 C 并嘗試從另一條路徑到 F。最后，我們找到了 G。
總的來說，在我們到達(dá)最深的結(jié)點之后，我們只會回溯并嘗試另一條路徑。
因此，你在 DFS 中找到的第一條路徑并不總是最短的路徑。例如，在上面的例子中，我們成功找出了路徑 A-> C-> F-> G 并停止了 DFS。但這不是從 A 到 G 的最短路徑。
2. 棧的入棧和退棧順序是什么？
我們首先將根結(jié)點推入到棧中；然后我們嘗試第一個鄰居 B 并將結(jié)點 B 推入到棧中；等等等等。當(dāng)我們到達(dá)最深的結(jié)點 E 時，我們需要回溯。當(dāng)我們回溯時，我們將從棧中彈出最深的結(jié)點，這實際上是推入到棧中的最后一個結(jié)點。
結(jié)點的處理順序是完全相反的順序，就像它們被添加到棧中一樣，它是后進先出（LIFO）。這就是我們在 DFS 中使用棧的原因。
正如我們在本章的描述中提到的，在大多數(shù)情況下，我們在能使用 BFS 時也可以使用 DFS。但是有一個重要的區(qū)別：遍歷順序。
與 BFS 不同，更早訪問的結(jié)點可能不是更靠近根結(jié)點的結(jié)點。因此，你在 DFS 中找到的第一條路徑可能不是最短路徑。
模板 - 遞歸
/*
* Return true if there is a path from cur to target.
*/
boolean DFS(Node cur, Node target, Set<Node> visited) {
return true if cur is target;
for (next : each neighbor of cur) {
if (next is not in visited) {
add next to visted;
return true if DFS(next, target, visited) == true;
}
}
return false;
}
當(dāng)我們遞歸地實現(xiàn) DFS 時，似乎不需要使用任何棧。但實際上，我們使用的是由系統(tǒng)提供的隱式棧，也稱為調(diào)用棧。
示例
讓我們看一個例子。我們希望在下圖中找到結(jié)點 0 和結(jié)點 3 之間的路徑。我們還會在每次調(diào)用期間顯示棧的狀態(tài)。
在每個堆棧元素中，都有一個整數(shù) cur，一個整數(shù) target，一個對訪問過的數(shù)組的引用和一個對數(shù)組邊界的引用，這些正是我們在 DFS 函數(shù)中的參數(shù)。我們只在上面的棧中顯示 cur。
每個元素都需要固定的空間。棧的大小正好是 DFS 的深度。因此，在最壞的情況下，維護系統(tǒng)棧需要 O(h)，其中 h 是 DFS 的最大深度。在計算空間復(fù)雜度時，永遠(yuǎn)不要忘記考慮系統(tǒng)棧。
在上面的模板中，我們在找到第一條路徑時停止。
如果你想找到最短路徑呢？
提示：再添加一個參數(shù)來指示你已經(jīng)找到的最短路徑。
