BFS与DFS

\_~~1；应用方面 \_ \_\_ \_ ——————bfs宽度搜索用于寻找最优解； ——— — —— dfs深度![]()搜索用于遍历寻找解； 2；实现原理； ——bfs；利用队列；层次来搜索的； ~~~~ 这里写图片描述 解释一下图片； 第一层；–A； 第二层；–BCD； 第三层；–EF； 第四层；–GH； 第4层；–I； 因为他是按层搜索，就是说只要bfs搜索到结果那么一定是最优解；； 来个题目化的；将上图CI连接，求从A到I最短路径；依旧划分层次；第三层就会搜到I；也就是说bfs最先搜到的一定是最优 解； 模板；//结合上图理解代码； Q={起点s}; 标记s为己访问; while (Q非空) { 取Q队首元素u; u出队; 所有与u相邻且未被访问的点进入队列; 标记u为已访问; ```cpp } //////////////////////////////////////////////////////////// whlie (队列不空) { u = 对队首元素； ``` 首元素出队； for (所有与 u 邻接点 v) // u 的上 下 左 右 // if(v 的坐标在 row, col之内 // 并且 v 不是墙 // 并且 v 未被遍历) v 入队 } 1 2 3 4 5 6~~~~~~~~ \_ \_ \_ \_ \_ \_ \_ \_ \_ \_\_ \_ \_ \_ \_ \_ \_ \_ \_ \_ ~~~~~~\_ 7 8 9 10 11 12 13 14 15 16 ——dfs；利用运用堆栈，递归层次搜索，回溯来遍历全部；  ------------ 这里写图片描述 解释一下图片； 利用回溯，一条道路走到底，然后返回上一级，继续进行搜索，直到搜索完毕； 模板；//结合上图理解代码； void DFS( Point P ){ for(所有P的邻接点K){ if(K未被访问){ 标记K; ```cpp DFS(K); //有时候要清空之前的标记； } } } ``` 1 2 3 4 5 6 7 8 9 版权声明：该版权来自某大佬