在正式进入图论前我们需要需要知道图的两种搜索方式——DFS(深度优先搜索)与BFS(广度优先搜索)
DFS
深度优先搜索的基本逻辑就是 —— 撞了南墙就回头
其主要需要理解的就是 “恢复” 过程,我们举例题说明:
此题没有什么巧妙的算法,我们只能用暴力方法一一列举,但你的计算机并不会,你需要告诉计算机怎么去一一列举。
我们以n = 3 画个图举个例:
那么DFS实际上的搜索路线如下:
#include <iostream>
const int N = 10;
int path[N]; //用来保存我们填上的数字
bool st[N]; //用来记录哪些值已经被使用过
int n;
void dfs(int u) //传入的参数为第u 个位置应该填什么
{
if(u>n) //当我们列举完,指针指向位置n+1 结束填写输出我们已经排列好的数字
{
for(int i = 1;i<=n;i++) std::cout<<path[i]<<" ";
std::cout<<std::endl;
return; //记得结束递归,否则将会无法结束列举而TLE
}
for(int i = 1;i<=n;i++)
{
if(!st[i]) //列举1 —— n中哪些数字还没有被用过,并将其填到数组中
{
path[u] = i;
st[i] = true;
dfs(u+1); //加深递归,看看下一个位置填什么
//后面的位置就是恢复的过程,记住,我们撞了南墙以后会回头,在此题也就是填完n 个数字后我们回头看看位置n-1是否还有其他填法,我们需要恢复到没有填位置n-1的状态。
path[u] = 0;
st[i] = false;
}
}
}
int main()
{
std::cin>>n;
dfs(1);
}