圖的搜索（一）：廣度優先搜索算法和深度優先搜索算法

本章主要記錄了圖的搜索算法，和可以解決圖的基本問題——最短路徑問題的算法。本章主要對圖搜索的相關算法進行了介紹：廣度優先搜索算法、深度優先搜索算法。

下一章將繼續介紹：貝爾曼-福特算法、狄克斯特拉算法、A*算法。

---

離散數學中的圖

上圖中的圓圈叫作“頂點”（也叫“結點”），連接頂點的線叫作“邊”。也就是說，由頂點和連接每對頂點的邊所構成的圖形就是圖。

加權圖

有權的邊就可以表示頂點之間的“連接程度”

有向圖

可以控制方向。

同時，有向圖也可與加權圖結合

根據搜索的順序不同,圖的搜索算法可分為“廣度優先搜索”和“深度優先搜索”這兩種。

廣度優先搜索

廣度優先搜索是一種對圖進行搜索的算法。假設我們一開始位于某個頂點（即起點），此時并不知道圖的整體結構，而我們的目的是從起點開始順著邊搜索，直到到達指定頂點（即終點）。在此過程中每走到一個頂點，就會判斷一次它是否為終點。廣度優先搜索會優先從離起點近的頂點開始搜索。

設置A為起點，G為終點。從A開始搜索，將可以從A直達的三個頂點BCD設為下一步候補頂點。

從候補頂點中選出一個頂點。優先選擇最早成為候補的那個頂點，如果多個頂點同時成為候補，那么可以隨意選擇其中一個。

此處選擇了B，繼續往下搜索。將可以從 B 直達的兩個頂點 E 和 F 設為候補頂點。**此時，最早成為候補頂點的是C和D，于是需要回到C和D繼續往下。**依次循環，直到找到目標點。

這個例子的搜索順序為：A、B、C、D、E、F、H、I、J、K。

注意：候補頂點是用“先入先出”(FIFO)的方式來管理的,因此可以使用“隊列”這個數據結構。（數據結構復習：鏈表、數組、棧、隊列、哈希表、堆、二叉樹-CSDN博客）

廣度優先搜索的特征為從起點開始，由近及遠進行廣泛的搜索。因此，目標頂點離起點越近，搜索結束得就越快。

*以上例子，沒有閉環的圖叫做“樹”。如果圖為閉環（起點和終點是同一個頂點），則搜索步驟相同。

深度優先算法

與廣度優先搜索不同，深度優先搜索會沿著一條路徑不斷往下搜索直到不能再繼續為止,然后再折返,開始搜索下一條候補路徑。

主要的區別在于候補頂點的選擇不同。與廣度優先搜索算法相同，起點從A開始，并從B、C、D開始往下選擇。隨機選擇了B后，候補頂點變為E、F。與廣度優先搜索算法不同的是，此處則繼續選擇最新成為候補頂點的點開始往下繼續搜索。

這個例子搜索順序為： A、B、E、K、F、C、H。

候補頂點是用“后入先出”（LIFO）的方式來管理的，因此可以使用“棧”這個數據結構。（數據結構復習：鏈表、數組、棧、隊列、哈希表、堆、二叉樹-CSDN博客）

深度優先搜索的特征為沿著一條路徑不斷往下，進行深度搜索。

參考資料：我的第一本算法書 (石田保輝 宮崎修一)