深度优先搜索的基本算法结构:递归实现 Procedure dfs try ■Fori:=1 to maxr do begin f子结点m符合条件then begin 产生的子结点m入栈; i子结点mr是目标结点then输出 else dfs try(i+1) 栈顶元素出栈; End ■End;
深度优先搜索的基本算法结构：递归实现 ◼ Procedure dfs_try(i); ◼ For i:=1 to maxr do ◼ begin ◼ if 子结点mr符合条件 then ◼ begin ◼ 产生的子结点mr入栈； ◼ if子结点mr是目标结点 then 输出； ◼ else dfs_try(i+1); ◼ 栈顶元素出栈； ◼ End; ◼ End;
深度优先搜索S到T的搜索路径 留们6:17PM @62PM 国 用步几229 图36搜索目标的深度优先图-7搜索目标的采度优先
◼ 深度优先搜索S到T的搜索路径 S T S T
(2广度优先路径搜索BFS 口广度优先搜索是在游戏中使用较多的一种搜索算法,其 基本思路是站在一个节点上,先将所有连接到该节点的 节点访问到,然后再继续访问下一层,直到找到目标为 节点2 Eg扫雷游戏 节点6节点5 节点4节点 叫 节点点力点6等节越 图8-8广度优先算法搜索过程
(2)广度优先路径搜索BFS ❑ 广度优先搜索是在游戏中使用较多的一种搜索算法，其 基本思路是站在一个节点上，先将所有连接到该节点的 节点访问到，然后再继续访问下一层，直到找到目标为 止。 Eg:扫雷游戏
BFS一广度优先搜索 A 氵/B BFS在访问了起始页点A之 后,由A出发,依次访问A的 各个未被访问过的邻接顶点 B,D,,c,然后再顺序访问 4(D C)3 : B,D,…,c的所有还未被访 问过的等接顶点。再从这些访 问过的项点出发,再访问它们 的所有还未被访问过的邻接顶 点,…如此做下去,直到图 中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜 索过程每向前走一步可能访 9问一批顶点
BFS – 广度优先搜索 BFS在访问了起始顶点A 之 后, 由 A 出发, 依次访问 A 的 各个未被访问过的邻接顶点 B, D,…, C, 然后再顺序访问 B, D, …, C 的所有还未被访 问过的邻接顶点。再从这些访 问过的顶点出发，再访问它们 的所有还未被访问过的邻接顶 点，… 如此做下去，直到图 中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜 索过程,每向前走一步可能访 问一批顶点。 A D C E G B F H I 1 2 4 3 5 6 7 8 9
BFS的代码分析 void BFSO queue< point>q;/队列 g push(st);初始点入队列 Whle(! g empty)爪队列中还有要处理的点 从队列中取出下一个处理的点p; for(p的所有邻接点) if该邻接点满足搜索条件) g- push邻接忘; 标记该邻接点为已访问
BFS的代码分析 void BFS() { queue<point> q;//队列 q.push(st);//初始点入队列 while(!q.empty())//队列中还有要处理的点 { 从队列中取出下一个处理的点p； for(p的所有邻接点) if(该邻接点满足搜索条件) { q.push(邻接点); 标记该邻接点为已访问； } } }