qidao123.com技术社区-IT企服评测·应用市场
标题:
【刷题】备战蓝桥杯 — dfs 算法
[打印本页]
作者:
伤心客
时间:
2025-4-23 13:46
标题:
【刷题】备战蓝桥杯 — dfs 算法
送给大家一句话：
风度真美！
即使流泪，也要鼓掌，
即使失望，也要满怀希望。
——刘宝增
1 前言
在蓝桥杯的角逐中，深度优先搜刮（DFS，Depth-First Search）算法是一种常用的搜刮算法，它通过尽大概深地搜刮树的分支，来探求解决方案。由于其简单和易于实现的特性，DFS成为解决题目的强盛工具，尤其是在数据规模较小的环境下。数据在100以内一般使用dfs
运行原理： DFS算法的核心头脑是从一个起点开始，沿着树的边走到尽大概深的分支上，然后回溯到之前的分叉点，探求未探索的分支。这个过程重复进行，直到找到解决方案或探索完全部大概的路径。DFS通常使用递归实现，这使得代码简洁易读。它利用栈（递归调用栈）来记载访问路径，从而实现回溯功能。根本蓝桥杯dfs算法题型可以使用以下模版：
#include <bits/stdc++.h>
//视情况而定
#define int long long
#define endl '\n'
#define N 1001
using namespace std;
//往往需要一个哈希表来辅助判断
int vis[N] = {
0};
void dfs()
{
//退出条件很重要！！！
if() return ;
for()
{
//跟新结果
//继续深入
dfs();
//回溯
}
}
signed main()
{
//加快读写速度 也可以直接使用C语言标准输入输出函数
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//多组数据
int t = 0; cin >> t;
while(t--)
{
//进行基础读入数据
//构建图 ，记录结构体等
//解决问题
dfs();
}
return 0；
}
复制代码
常用于以下题型：
路径题目： 探求从起点到尽头的路径，或者求解全部大概的路径。
排列组合题目： 须要罗列出全部大概的环境时，如全排列、组合选择。
连通性题目： 如判断图中两个节点是否连通，或者求解连通分量。
解谜与回溯题目： 如N 皇后题目、迷宫探索、数独解题等。
注意事项：
栈溢出题目（一般不消思量）： 由于DFS使用递归实现，深度过大时大概会导致栈溢出。针对这一点，可以实行使用迭代深化搜刮（IDS）或非递归方式实现DFS。
重复状态处置惩罚（一定要细致）： 在搜刮过程中大概会遇到重复状态，如果不加以处置惩罚，大概会导致算法陷入无限循环。通常使用访问标记（如访问数组）来制止重复访问。
选择符合的剪枝策略（尽力而行）： 合理的剪枝可以明显进步DFS的效率。通过预先判断某些路径是否大概到达目标，从而制止无效搜刮。
通过以上的解析，我们可以看到DFS不仅在蓝桥杯中，在许多算法竞赛和实际题目解决中都是一个非常实用的工具。它固然在处置惩罚大数据量时大概会遇到性能瓶颈，但在数据量适中、须要深度搜刮解决方案的题目上，DFS仍然是一个非常可靠的选择。
下面我们来一起做几道竞赛题目来试试手！
2 洛谷 P1030 [NOIP2001 普及组] 求先序排列
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）
输入格式
共两行，均为大写字母构成的字符串，表示一棵二叉树的中序与后序排列。
输特别式
共一行一个字符串，表示一棵二叉树的先序。
根据题目，我们须要通过二叉树的中序遍历和后序遍历来写出前序遍历的结果。对于二叉树的确定单凭中序遍历或者后序遍历是不大概的，只有两者联合才能确定一棵完备的二叉树！来看样例：
输入
BADC
BDCA
输出
ABCD
我们可以画出树的布局：
这样前序遍历的结果就有了
算法思路
这道题涉及了二叉树，那么如果不使用dfs 就会非常复杂捏！以是我们把解题交给dfs,重重递归解决题目：
起首通事后序遍历 ， 我们可以确定根节点 （输出打印）
通过在中序遍历中找到根节点的位置，可以区分左右子树
区分出左右子树后，就可以继续探求左右子树的根节点 ，重复1 - 2操纵即可。
#include<iostream>
#include<string>
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)
Powered by Discuz! X3.4
