20250901 搜索总结

引子

什么叫搜索？就是通过一定的顺序经过点之间的边到达图上的其他点。进行图上枚举时，通常需要遵循特定的顺序。例如，当寻找两点之间的路径时，必须严格按照图的边进行枚举。

深度优先搜索

深度优先搜索(DFS)主要特点是不撞南墙不回头，就是每次找出一条没有走过的边继续搜索，直到没有边可走了就开始回溯，回到上一个点，继续搜索。

对于某些节点，只需搜索一次即可，但需额外判断目标节点是否已被搜索过。

有些题目表面上看不出与图相关，但可以通过状态空间来理解。将其建模为图结构后，就能在对应的图上进行搜索。

实际操作中，通常不需要显式构建整张图，只需在每个状态(顶点)处找出所有可能的转移(边)即可.

例题，求n的全排列。

#include<bits/stdc++.h>
using namespace std;
int a[10],n;
bool f[10];
void dfs(int k){if(k>n){//如果目标数组长度为nfor(int i=1;i<=n;i++){//直接输出cout<<"    "<<a[i];}cout<<endl;return;//别跑了}for(int i=1;i<=n;i++){//查看每一个数if(!f[i]){//如果没有用过f[i]=1;//把他用了a[k]=i;//记录dfs(k+1);//继续深搜f[i]=0;//把他还回去}}
}
int main(){cin>>n;dfs(1);return 0;
} 

广度优先搜索

广度优先搜索(BFS)他的搜索策略就不一样了，它首先把周围的点跑一边然后再找离他最近的一个点继续广搜。总结起来就是先近后远。

写的时候要用一个队列实现，这个队列用来存储即将要搜索的节点。

首先从一个点出发，把他放到队列里，然后每次拿到队列开头，看可以到哪里去，就把能到的点放到队列里去，循环直到队列为空。

由于队列遵循先进先出的原则，距离起点较近的节点会优先入队，因此每次取出的队头始终是离起点最近的节点。

在求解无权图的最短路径时，BFS是最佳选择，因为它能确保首次访问某个节点时，该路径必定是最短路径。