Unity面试八股文之寻路算法BFS广度优先搜索

---

广度优先搜索（Breadth-First Search, BFS）算法

BFS算法是一种用于图或树的遍历算法。它逐层扩展节点，从起始节点开始，首先访问其所有邻居节点，然后再逐层向外扩展。

步骤剖析：

• 假如出发点设为A，O为终点。

• 根据上右下左来找领近节点，A点的领近节点为B、C, 判断不是目标点O继续搜索

• 根据上右下左来找领近节点，B点的领近节点为E、D, C点的领近节点为F(D已经在B点找到了，不算入在内), 判断不是目标点O继续搜索

• 从E点开始继续搜索，则找到Q、G，D点则找到H，F点则找到I

• 从G点开始搜索，找到了X、G点则找到了L，H点则找到了K，I点则找到了N，找不到终点0继续搜索下去

• 从X点搜索，找到了T、L点则找到了O（只是找到了，还没轮到O点作判断），K点找到了M、N点找到了M，但是M点已经在K点被找到了，所以不计

• T点找到了U，而O点则是已经被找到了，搜索到此停止，M点找到的是P点。

只需要逆推一下就能找到路径

A -> B -> E -> G -> L -> O

---

enjoy it ~