“`类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2……Vit，并均标记为已访问过，然后再按照Vi1、Vi2……Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。
对于状态数很多时，广度优先搜索可以采用循环队列或动态链表来处理，对于这两种搜索算法，其主要区别如下表：
<figure><table><thead><tr><th>遍历方式</th><th>深度优先搜索遍历</th><th>广度优先搜索遍历</th></tr></thead><tbody><tr><td>所用数据结构</td><td>栈</td><td>队列</td></tr><tr><td>一般优化</td><td>最优性剪枝可行性剪枝</td><td>Hash判重双向搜索</td></tr></tbody></table></figure>
“`
Was this helpful?
0 / 0