隊(duì)列和廣度優(yōu)先搜索(BFS)骇陈、棧和深度優(yōu)先搜索(DFS)及Java模板

本文為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
}
  1. 如代碼所示浇垦,在每一輪中炕置,隊(duì)列中的結(jié)點(diǎn)是等待處理的結(jié)點(diǎn)。
  2. 在每個更外一層的 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
}

有兩種情況你不需要使用哈希集:

  1. 你完全確定沒有循環(huán)韭寸,例如春哨,在樹遍歷中;
  2. 你確實(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)如庭。

Stack Status

在每個堆棧元素中,都有一個整數(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)找到的最短路徑苍狰。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市烘绽,隨后出現(xiàn)的幾起案子淋昭,更是在濱河造成了極大的恐慌,老刑警劉巖安接,帶你破解...
    沈念sama閱讀 211,042評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件翔忽,死亡現(xiàn)場離奇詭異,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)歇式,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,996評論 2 384
  • 文/潘曉璐 我一進(jìn)店門矢赁,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人贬丛,你說我怎么就攤上這事撩银。” “怎么了豺憔?”我有些...
    開封第一講書人閱讀 156,674評論 0 345
  • 文/不壞的土叔 我叫張陵额获,是天一觀的道長。 經(jīng)常有香客問我恭应,道長抄邀,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,340評論 1 283
  • 正文 為了忘掉前任昼榛,我火速辦了婚禮境肾,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘胆屿。我一直安慰自己奥喻,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,404評論 5 384
  • 文/花漫 我一把揭開白布非迹。 她就那樣靜靜地躺著环鲤,像睡著了一般。 火紅的嫁衣襯著肌膚如雪憎兽。 梳的紋絲不亂的頭發(fā)上冷离,一...
    開封第一講書人閱讀 49,749評論 1 289
  • 那天,我揣著相機(jī)與錄音纯命,去河邊找鬼西剥。 笑死,一個胖子當(dāng)著我的面吹牛亿汞,可吹牛的內(nèi)容都是我干的瞭空。 我是一名探鬼主播,決...
    沈念sama閱讀 38,902評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼留夜,長吁一口氣:“原來是場噩夢啊……” “哼匙铡!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起碍粥,我...
    開封第一講書人閱讀 37,662評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎黑毅,沒想到半個月后嚼摩,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,110評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,451評論 2 325
  • 正文 我和宋清朗相戀三年枕面,在試婚紗的時候發(fā)現(xiàn)自己被綠了愿卒。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,577評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡潮秘,死狀恐怖琼开,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情枕荞,我是刑警寧澤柜候,帶...
    沈念sama閱讀 34,258評論 4 328
  • 正文 年R本政府宣布,位于F島的核電站躏精,受9級特大地震影響渣刷,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜矗烛,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,848評論 3 312
  • 文/蒙蒙 一辅柴、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧瞭吃,春花似錦碌嘀、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,726評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至牡拇,卻和暖如春魁瞪,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背惠呼。 一陣腳步聲響...
    開封第一講書人閱讀 31,952評論 1 264
  • 我被黑心中介騙來泰國打工导俘, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人剔蹋。 一個月前我還...
    沈念sama閱讀 46,271評論 2 360
  • 正文 我出身青樓旅薄,卻偏偏與公主長得像,于是被迫代替她去往敵國和親泣崩。 傳聞我的和親對象是個殘疾皇子少梁,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,452評論 2 348

推薦閱讀更多精彩內(nèi)容

  • 數(shù)據(jù)結(jié)構(gòu)與算法--圖的搜索(深度優(yōu)先和廣度優(yōu)先) 有時候我們需要系統(tǒng)地檢查每一個頂點(diǎn)或者每一條邊來獲取圖的各種性質(zhì)...
    sunhaiyu閱讀 2,609評論 0 5
  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系,并對這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算矫付,而且確保經(jīng)過這...
    Winterfell_Z閱讀 5,690評論 0 13
  • 這世間有愛情买优、親情妨马、友情挺举,每個人都會擁有,也會用自己的親身經(jīng)歷去詮釋它們的滋味烘跺。然而湘纵,有一種情卻與上述無...
    君子蘭_fcb0閱讀 351評論 2 3
  • 關(guān)于人工智能,它擁有強(qiáng)大的計(jì)算能力滤淳,無限的存儲空間梧喷;上知天文下知地理無所不知,根據(jù)各種數(shù)據(jù)和數(shù)學(xué)模型預(yù)測未來脖咐;AI...
    gabz閱讀 373評論 0 1
  • 這個世界上有很多故事铺敌,而平凡如我卻不是圭多,幸好你成為了我的多拉文搂。 我的情緒向來波動不平适刀,想來只怕是因?yàn)槊恳粋€在愛...
    松果好吃么閱讀 161評論 0 1