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)演算法，实用的节点搜寻法

好啦！今天就先到这边啦～还是在家野餐吹冷气最浪漫。明天见掰掰～