Aloha！又是我少女人妻 Uerica！今天真是個秋高氣爽的日子，下午想說跟老公去公園浪漫野餐，還特地開到人煙稀少的公園。結果食物都還沒吃幾口，頭髮就被吹得亂七八糟，盒子還差點飛走，一點都不浪漫啦～

圖形搜尋法 Graph Searching Methods

前面有提到圖型結構是由節點 node 和邊 edge 組成的非線性結構，若沒有封閉迴圈，且每個子節點都只有一個父節點的情況稱為樹，而樹又是圖形結構的一種。

圖與樹的搜尋演算法與一般的陣列搜尋演算法會有些不同，下列就來介紹哪些搜尋演算法適合用在圖形或樹狀的資料結構中。

延伸閱讀：Day 11 資料結構：圖 Graph

常見的圖形搜尋演算法

廣度優先搜尋 Breadth-First Search , BFS

廣度優先搜尋，又稱寬度優先搜尋，或橫向優先搜尋。此搜尋方式是用先進先出 (FIFO) 的方式，所以可用佇列的資料結構來存放資料。廣度優先搜尋是從離根節點較近的節點開始搜尋，若沒有會再往下一層搜尋，直到找到搜尋目標或全部搜尋完為止。因為這樣的特性，若搜尋目標離根節點很近，越快被搜尋到。

• 假設搜尋目標為 5 ，從根節點 1 開始。
  

• 往下搜尋所有子節點，這邊先從左邊的子節點 2 開始
  

• 再搜尋右邊子節點 3
  

• 都不是會再往下一層延伸，先從節點 2 的子節點 4 開始
  

• 若不是再搜尋節點 5 ，比對後找到搜尋目標
  

深度優先搜尋 Depth-first Search , DFS

深度優先搜尋會先從根節點出發，鎖定某節點後，將其子節點與子孫節點都搜尋完成，才會再延伸至兄弟節點，以此類推。深度優先搜尋是用後進先出 LIFO 的方式，所以可用堆疊的資料結構來存放資料。

• 從根節點 1 開始搜尋
  

• 若不是搜尋目標，往下搜尋子節點 2
  

• 若不是搜尋目標，再往下深入搜尋節點 4
  

• 若不是搜尋目標，再往下深入搜尋節點 8
  

• 若不是才退回上層，搜尋節點 5 ，找到搜尋目標
  

參考資料：

維基百科：廣度優先搜尋

JavaScript 學演算法（十二）- 樹 & 二元樹

深度優先搜尋(DFS)和廣度優先搜尋(BFS)演算法，實用的節點搜尋法

好啦！今天就先到這邊啦～還是在家野餐吹冷氣最浪漫。明天見掰掰～