本文為Leetcode學(xué)習(xí)筆記
隊(duì)列和廣度優(yōu)先搜索(BFS)
廣度優(yōu)先搜索(BFS)的一個常見應(yīng)用是找出從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最短路徑震庭。在本文中,我們提供了一個示例來解釋在 BFS 算法中是如何逐步應(yīng)用隊(duì)列的你雌。
1. 結(jié)點(diǎn)的處理順序是什么器联?
在第一輪中,我們處理根結(jié)點(diǎn)婿崭。在第二輪中拨拓,我們處理根結(jié)點(diǎn)旁邊的結(jié)點(diǎn);在第三輪中氓栈,我們處理距根結(jié)點(diǎn)兩步的結(jié)點(diǎn)渣磷;等等等等。
與樹的層序遍歷類似授瘦,越是接近根結(jié)點(diǎn)的結(jié)點(diǎn)將越早地遍歷醋界。
如果在第 k 輪中將結(jié)點(diǎn) X 添加到隊(duì)列中竟宋,則根結(jié)點(diǎn)與 X 之間的最短路徑的長度恰好是 k。也就是說形纺,第一次找到目標(biāo)結(jié)點(diǎn)時丘侠,你已經(jīng)處于最短路徑中。
2. 隊(duì)列的入隊(duì)和出隊(duì)順序是什么逐样?
我們首先將根結(jié)點(diǎn)排入隊(duì)列婉陷。然后在每一輪中,我們逐個處理已經(jīng)在隊(duì)列中的結(jié)點(diǎn)官研,并將所有鄰居添加到隊(duì)列中秽澳。值得注意的是,新添加的節(jié)點(diǎn)不會立即遍歷戏羽,而是在下一輪中處理担神。
結(jié)點(diǎn)的處理順序與它們添加到隊(duì)列的順序是完全相同的順序,即先進(jìn)先出(FIFO)始花。這就是我們在 BFS 中使用隊(duì)列的原因妄讯。
在特定問題中執(zhí)行 BFS 之前確定結(jié)點(diǎn)和邊緣非常重要。通常酷宵,結(jié)點(diǎn)將是實(shí)際結(jié)點(diǎn)或是狀態(tài)亥贸,而邊緣將是實(shí)際邊緣或可能的轉(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
}
- 如代碼所示浇垦,在每一輪中炕置,隊(duì)列中的結(jié)點(diǎn)是等待處理的結(jié)點(diǎn)。
- 在每個更外一層的 while 循環(huán)之后男韧,我們距離根結(jié)點(diǎn)更遠(yuǎn)一步朴摊。變量 step 指示從根結(jié)點(diǎn)到我們正在訪問的當(dāng)前結(jié)點(diǎn)的距離。
模板II
有時此虑,確保我們永遠(yuǎn)不會訪問一個結(jié)點(diǎn)兩次很重要甚纲。否則,我們可能陷入無限循環(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)韭寸,例如春哨,在樹遍歷中;
- 你確實(shí)希望多次將結(jié)點(diǎn)添加到隊(duì)列中棒仍。
棧和深度優(yōu)先搜索(DFS)
與 BFS 類似悲靴,深度優(yōu)先搜索(DFS)也可用于查找從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑。在本文中,我們提供了示例來解釋 DFS 是如何工作的以及棧是如何逐步幫助 DFS 工作的癞尚。
圖
1. 結(jié)點(diǎn)的處理順序是什么耸三?
在上面的例子中,我們從根結(jié)點(diǎn) A 開始浇揩。首先仪壮,我們選擇結(jié)點(diǎn) B 的路徑,并進(jìn)行回溯胳徽,直到我們到達(dá)結(jié)點(diǎn) E积锅,我們無法更進(jìn)一步深入。然后我們回溯到 A 并選擇第二條路徑到結(jié)點(diǎn) C 养盗。從 C 開始缚陷,我們嘗試第一條路徑到 E 但是 E 已被訪問過。所以我們回到 C 并嘗試從另一條路徑到 F往核。最后箫爷,我們找到了 G。
總的來說聂儒,在我們到達(dá)最深的結(jié)點(diǎn)之后虎锚,我們只會回溯并嘗試另一條路徑。
因此衩婚,你在 DFS 中找到的第一條路徑并不總是最短的路徑窜护。例如,在上面的例子中非春,我們成功找出了路徑 A-> C-> F-> G 并停止了 DFS柱徙。但這不是從 A 到 G 的最短路徑。
2. 棧的入棧和退棧順序是什么税娜?
我們首先將根結(jié)點(diǎn)推入到棧中坐搔;然后我們嘗試第一個鄰居 B 并將結(jié)點(diǎn) B 推入到棧中藏研;等等等等敬矩。當(dāng)我們到達(dá)最深的結(jié)點(diǎn) E 時,我們需要回溯蠢挡。當(dāng)我們回溯時弧岳,我們將從棧中彈出最深的結(jié)點(diǎn),這實(shí)際上是推入到棧中的最后一個結(jié)點(diǎn)业踏。
結(jié)點(diǎn)的處理順序是完全相反的順序禽炬,就像它們被添加到棧中一樣,它是后進(jìn)先出(LIFO)勤家。這就是我們在 DFS 中使用棧的原因腹尖。
正如我們在本章的描述中提到的,在大多數(shù)情況下伐脖,我們在能使用 BFS 時也可以使用 DFS热幔。但是有一個重要的區(qū)別:遍歷順序乐设。
與 BFS 不同,更早訪問的結(jié)點(diǎn)可能不是更靠近根結(jié)點(diǎn)的結(jié)點(diǎn)绎巨。因此近尚,你在 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)我們遞歸地實(shí)現(xiàn) DFS 時场勤,似乎不需要使用任何棧戈锻。但實(shí)際上,我們使用的是由系統(tǒng)提供的隱式棧和媳,也稱為調(diào)用棧格遭。
示例
讓我們看一個例子。我們希望在下圖中找到結(jié)點(diǎn) 0 和結(jié)點(diǎn) 3 之間的路徑留瞳。我們還會在每次調(diào)用期間顯示棧的狀態(tài)如庭。
在每個堆棧元素中,都有一個整數(shù) cur撼港,一個整數(shù) target坪它,一個對訪問過的數(shù)組的引用和一個對數(shù)組邊界的引用,這些正是我們在 DFS 函數(shù)中的參數(shù)帝牡。我們只在上面的棧中顯示 cur往毡。
每個元素都需要固定的空間。棧的大小正好是 DFS 的深度靶溜。因此开瞭,在最壞的情況下,維護(hù)系統(tǒng)棧需要 O(h)罩息,其中 h 是 DFS 的最大深度嗤详。在計(jì)算空間復(fù)雜度時,永遠(yuǎn)不要忘記考慮系統(tǒng)棧瓷炮。
在上面的模板中葱色,我們在找到第一條路徑時停止。
如果你想找到最短路徑呢娘香?
提示:再添加一個參數(shù)來指示你已經(jīng)找到的最短路徑苍狰。