【刷题】备战蓝桥杯 — dfs 算法

送给大家一句话：
风度真美！
即使流泪，也要鼓掌，
即使失望，也要满怀希望。
——刘宝增

  
1 前言

在蓝桥杯的角逐中，深度优先搜刮（DFS，Depth-First Search）算法是一种常用的搜刮算法，它通过尽大概深地搜刮树的分支，来探求解决方案。由于其简单和易于实现的特性，DFS成为解决题目的强盛工具，尤其是在数据规模较小的环境下。数据在100以内一般使用dfs
运行原理： DFS算法的核心头脑是从一个起点开始，沿着树的边走到尽大概深的分支上，然后回溯到之前的分叉点，探求未探索的分支。这个过程重复进行，直到找到解决方案或探索完全部大概的路径。DFS通常使用递归实现，这使得代码简洁易读。它利用栈（递归调用栈）来记载访问路径，从而实现回溯功能。根本蓝桥杯dfs算法题型可以使用以下模版：

1. #include <bits/stdc++.h>
2. //视情况而定
3. #define int long long
4. #define endl '\n'
5. #define N 1001
7. using namespace std;
8. //往往需要一个哈希表来辅助判断
9. int vis[N] = {
10.    0};
11. void dfs()
12. {
13.    
14.         //退出条件很重要！！！
15.         if() return ;
16.         for()
17.         {
18.    
19.                 //跟新结果
20.                 //继续深入
21.                 dfs();
22.                 //回溯
23.         }
24. }
26. signed main()
27. {
28.    
29.         //加快读写速度 也可以直接使用C语言标准输入输出函数
30.         ios::sync_with_stdio(0);
31.         cin.tie(0);
32.         cout.tie(0);
33.         //多组数据
34.         int t = 0; cin >> t;
35.         while(t--)
36.         {
37.    
38.                 //进行基础读入数据
39.                 //构建图 ，记录结构体等
40.                 //解决问题
41.                 dfs();
42.         }
43.         return 0；
44. }

复制代码

常用于以下题型：

• 路径题目： 探求从起点到尽头的路径，或者求解全部大概的路径。
  
• 排列组合题目： 须要罗列出全部大概的环境时，如全排列、组合选择。
  
• 连通性题目： 如判断图中两个节点是否连通，或者求解连通分量。
  
• 解谜与回溯题目： 如N 皇后题目、迷宫探索、数独解题等。
  

注意事项：

• 栈溢出题目（一般不消思量）： 由于DFS使用递归实现，深度过大时大概会导致栈溢出。针对这一点，可以实行使用迭代深化搜刮（IDS）或非递归方式实现DFS。
  
• 重复状态处置惩罚（一定要细致）： 在搜刮过程中大概会遇到重复状态，如果不加以处置惩罚，大概会导致算法陷入无限循环。通常使用访问标记（如访问数组）来制止重复访问。
  
• 选择符合的剪枝策略（尽力而行）： 合理的剪枝可以明显进步DFS的效率。通过预先判断某些路径是否大概到达目标，从而制止无效搜刮。
  

通过以上的解析，我们可以看到DFS不仅在蓝桥杯中，在许多算法竞赛和实际题目解决中都是一个非常实用的工具。它固然在处置惩罚大数据量时大概会遇到性能瓶颈，但在数据量适中、须要深度搜刮解决方案的题目上，DFS仍然是一个非常可靠的选择。
下面我们来一起做几道竞赛题目来试试手！
2 洛谷 P1030 [NOIP2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）
输入格式
共两行，均为大写字母构成的字符串，表示一棵二叉树的中序与后序排列。
输特别式
共一行一个字符串，表示一棵二叉树的先序。
根据题目，我们须要通过二叉树的中序遍历和后序遍历来写出前序遍历的结果。对于二叉树的确定单凭中序遍历或者后序遍历是不大概的，只有两者联合才能确定一棵完备的二叉树！来看样例：

• 输入
  BADC
  BDCA
  
• 输出
  ABCD
  

我们可以画出树的布局：

这样前序遍历的结果就有了
算法思路

这道题涉及了二叉树，那么如果不使用dfs 就会非常复杂捏！以是我们把解题交给dfs,重重递归解决题目：

• 起首通事后序遍历 ， 我们可以确定根节点 （输出打印）
  
• 通过在中序遍历中找到根节点的位置，可以区分左右子树
  
• 区分出左右子树后，就可以继续探求左右子树的根节点 ，重复1 - 2操纵即可。
  

1. #include<iostream>
2. #include<string>

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。