Monodyee

这个屌丝很懒，什么也没留下！

热门标签

2024/1/30 dfs与bfs

作者：Monodyee | 2024-02-26 18:23:54

踩

2024/1/30 dfs与bfs

想要了解dfs与bfs，就得了解队列和栈。

一、栈与队列

1.栈

栈说白了就是先入后出。把栈类比为一个容器。只有一个口，所以如果我们想要取出最底层也就是最先放入的元素，只能最后取出它。

栈基础操作有如下几种：

push 放入
pop 拿出
empty 是否为空
size 栈的大小
top 获取栈顶元素

下面将用两种方式实现：

用数组或者链表模拟栈


#include <iostream>
using namespace std;
 
const int N = 100;
 
int stk[N], top = 0;
 
int main()
{
 
	//使用数组模拟栈
	int x;
	cin >> x;
	//push放入栈中
	stk[++top] = x;
	//输出栈顶元素
	cout << stk[top] << endl;
	//pop拿出(不管top元素删不删，top--就行)
	top--;
	// 常用的就是，获取栈顶元素的同时，弹出栈顶元素
	int u = stk[top--];
 
 
	return 0;
}

以上是普通静态数组。但是考虑到现实生活由于入栈的元素可能会源源不断地增加，因此我们可以使用动态数组或者链表，这样就无须自行处理数组扩容问题。这里贴出hello算法里对这个的网址。https://www.hello-algo.com/chapter_stack_and_queue/stack/#1https://www.hello-algo.com/chapter_stack_and_queue/stack/#1

stl库写栈

首先就是 #include <stack>

定义：stack<数据类型> stk;

使用：

stk.push(x);
stk.pop();
stk.top();
stk.empty();//true表示空
stk.size();//返回正整数


#include <iostream>
#include <stack>
using namespace std;
 
 
int main()
{
	stack<int>stk;
	int x;
	cin >> x;
	//放入栈中
	stk.push(x);
	//输出栈顶
	cout << stk.top() << endl;
	//弹出栈顶
	stk.pop();
	return 0;
}

2.队列

队列则是：“先入先出”。「队列 queue」是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

队列基础操作有如下几种：

push 放入（从队尾）
pop 拿出（从队首）
empty 是否为空
size 栈的大小
front


#include <iostream>
using namespace std;
 
const int N = 100;
 
int q[N], front = 0, tail = 0;
 
int main()
{
 
	//使用数组模拟队列
	int x;
	cin >> x;
	//push 放入队列中
	q[++tail] = x;
	//pop 把元素移除（只能从队首）
	front++;
	//size 队列长度
	int size = tail - front + 1;
	//empty 看size是否为0
	//front 
	return q[front];
 
 
	return 0;
}


/* 初始化队列 */
queue<int> queue;
 
/* 元素入队 */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);
 
/* 访问队首元素 */
int front = queue.front();
 
/* 元素出队 */
queue.pop();
 
/* 获取队列的长度 */
int size = queue.size();
 
/* 判断队列是否为空 */
bool empty = queue.empty();

额外：优先队列，双向队列

http://t.csdnimg.cn/KpFjNhttp://t.csdnimg.cn/KpFjN 5.2 队列 - Hello 算法 (hello-algo.com)https://www.hello-algo.com/chapter_stack_and_queue/queue/#521 5.3 双向队列 - Hello 算法 (hello-algo.com)https://www.hello-algo.com/chapter_stack_and_queue/deque/


/* 初始化双向队列 */
deque<int> deque;
 
/* 元素入队 */
deque.push_back(2);   // 添加至队尾
deque.push_back(5);
deque.push_back(4);
deque.push_front(3);  // 添加至队首
deque.push_front(1);
 
/* 访问元素 */
int front = deque.front(); // 队首元素
int back = deque.back();   // 队尾元素
 
/* 元素出队 */
deque.pop_front();  // 队首元素出队
deque.pop_back();   // 队尾元素出队
 
/* 获取双向队列的长度 */
int size = deque.size();
 
/* 判断双向队列是否为空 */
bool empty = deque.empty();

双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。

我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 50 步）。当栈的长度超过 50 时，软件需要在栈底（队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。

二、DFS深度优先搜索-----栈

1.指数型搜索

模板：

void dfs(int step){
   判断边界
   尝试每一种可能 for(i=1;i<=n;i++){
       继续下一步 dfs(step+1)
       }
   返回
}


#include <iostream>
 
using namespace std;
 
const int N = 100;
 
int n;//输入的节点数  
int st[N] = {}; //决策数组 0 表示没有搜索过， 1表示选择 ， 2表示没有选择
 
// 对于每一个点，都需要有一次决策，无论是1还是2 
// 搜索是把所有的情况都考虑 
 
 // u表示对u进行抉择，已经抉择了u个数
void dfs(int u) {
	// 递归出口，当所有节点都决策完毕时输出结果  
	if (u > n){
		for (int i = 0; i < n; i++) {
			// 只有当第i个节点被选择时才输出 
			if (st[u] = 1){
				cout << i << " ";
			}
		}
 
	}
	// 选择第u个节点（标记为1）并继续搜索下一个节点
	st[u] = 1;
	dfs(u + 1);
 
	// 恢复第u个节点的状态（标记为0）并选择不选择第u个节点（标记为2）并继续搜索下一个节点
	st[u] = 0;
	st[u] = 2;
	dfs(u + 1);
	// 继续恢复第u个节点的状态（标记为0）以备下次决策使用  
	st[u] = 0;
}
int main()
{
	cin >> n;
	dfs(1);
	return 0;
}

例题1 P2036 Perket

P2036 [COCI2008-2009 #2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P2036


#include <iostream>  
#include <algorithm>  
#include <cstdio>  
#include <cmath>  
using namespace std;  
  
// 全局变量声明  
int n; // n代表数字的个数  
int mindif = 999999999; // mindif用于存储最小差值，初始化为一个非常大的数  
int s[10], b[10]; // s数组和b数组分别用于存储输入的数字和它们对应的值  
  
// perket函数是一个递归函数，用于计算所有可能的组合  
// u代表当前处理的数字的索引  
// sp代表当前选择的s数组中数字的乘积  
// bs代表当前选择的b数组中数字的和  
void perket(int u, int sp, int bs) {  
    // 递归终止条件：当u大于n时，表示所有数字都已经处理完毕  
    if (u > n) {  
        // 如果bs为0，表示没有选择任何b数组中的数字，直接返回  
        if (!bs) {  
            return;  
        }  
        // 更新最小差值  
        mindif = min(mindif, abs(sp - bs));  
        return;  
    }  
      
    // 递归调用1：不选择当前数字  
    perket(u + 1, sp, bs);  
      
    // 递归调用2：选择当前数字  
    perket(u + 1, sp * s[u], bs + b[u]);  
}  
  
int main() {  
    // 输入数字的个数  
    cin >> n;  
      
    // 输入每个数字及其对应的值  
    for (int i = 1; i <= n; i++) {  
        cin >> s[i] >> b[i];  
    }  
      
    // 调用perket函数开始计算  
    perket(1, 1, 0);  
      
    // 输出最小差值  
    cout << mindif << endl;  
      
    return 0;  
}

在给定的代码中，每次递归的两种选择（选择当前数字和不选择当前数字）可能会产生重复的结果。这意味着，递归函数perket可能会计算出重复的组合。

为了解决这个问题，可以在递归过程中添加一些逻辑来跳过已经计算过的组合，或者使用其他方法来避免重复计算。例如，可以维护一个集合或哈希集合来跟踪已经计算过的组合，并在递归函数中进行检查。

如果不采取措施避免重复计算，则可能会导致递归函数的时间复杂度增加，因为重复计算相同的组合会导致更多的递归调用。在处理大量数据时，这可能会导致性能问题。

2.组合型搜索

例题2 全排列

【题意】
先给一个正整数 ( 1 < = n < = 10 )，输出所有全排列。
什么是全排列，例如n＝3，输出所有组合,并且按字典序输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格）
【输入格式】
一行一个整数n。
【输出格式】
输出1~n的所有全排列。
【样例输入】
3
【样例输出】
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1


#include <iostream>  // 引入输入输出流库  
#include <algorithm>  // 引入算法库  
#include <cstdio>      // 引入标准输入输出库  
#include <cmath>        // 引入数学库  
using namespace std;     // 使用标准命名空间  
  
int n, ans[10], used[10];   // 定义全局变量，n表示要选取的数字个数，ans数组用于存放结果，used数组用于标记数字是否被使用过  
  
void dfs(int cnt){          // 定义深度优先搜索函数，cnt表示当前已经选取的数字个数  
    if (cnt > n) {           // 如果已经选取的数字个数大于n，说明已经选取了所有数字，输出结果并返回  
        for (int i = 1; i <= n; i++) { // 遍历所有数字并输出  
            cout << ans[i] << " ";  
        }  
        cout << endl;  
        return;  
    }  
    for (int i = 1; i <= n; i++){ // 枚举所有数字  
        if (used[i] == 0) {      // 如果数字i还没有被使用过  
            ans[cnt] = i;        // 将数字i放入当前位置  
            used[i] = 1;          // 标记数字i为已使用  
            dfs(cnt + 1);        // 递归搜索下一个位置  
               
            ans[cnt] = 0;         // 撤销当前位置的选择，即清空当前位置  
            used[i] = 0;           // 撤销对数字i的选择，即将其标记为未使用  
        }  
    }  
}  
  
int main() {                  // 主函数  
    cin >> n;                  // 输入要选取的数字个数n  
    dfs(1);                     // 从第一个位置开始搜索  
    return 0;                   // 程序正常结束  
}

这段代码中的回溯是通过以下步骤实现的：

1. 在dfs函数中，首先检查是否已经选取了所有数字（即`cnt`是否大于`n`）。如果是，则输出当前结果并返回。
2. 然后，函数使用一个循环来枚举所有数字。如果某个数字还没有被使用过（即`used[i]`等于0），则进行以下操作：

将该数字放入当前位置（即`ans[cnt] = i`）。
标记该数字为已使用（即`used[i] = 1`）。
递归调用`dfs(cnt + 1)`来搜索下一个位置。

3. 在递归调用返回后，执行回溯操作：

撤销当前位置的选择，即将`ans[cnt]`重置为0，表示该位置还没有被选择。
撤销对数字`i`的选择，即将`used[i]`重置为0，表示数字`i`现在可以再次被选择。

4. 重复上述过程，直到所有可能的排列都被探索完为止。

通过这种方式，代码能够撤销之前的决策，尝试其他可能的路径，从而全面地探索所有可能的解空间。

还有几个题，以后补补（太赶了qaq

三、BFS广度优先搜索-----队列

bfs个人感觉就是，同时往每个方向都试试，最先得到的就是最好的。

它是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。宽度优先搜索是一种对图进行搜索的算法。假设我们一开始位于某个顶点（即起点），此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点（即终点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。

b站有个视频非常清晰，这里贴下链接

【广度优先搜索BFS遍历-动画演示过程，希望对大家有所帮助~】

https://www.bilibili.com/video/BV1bP4y1K7Tr?vd_source=7ccfb0770f378b7710213a50fbacfc17https://www.bilibili.com/video/BV1bP4y1K7Tr?vd_source=7ccfb0770f378b7710213a50fbacfc17

这个大佬写的也很清晰：

http://t.csdnimg.cn/sw4pZhttp://t.csdnimg.cn/sw4pZ

int BFS(Node start, Node target) {
入队(初始状态);
visited[初始状态] = true;
while(!空队) {
for() { // 状态转换
Node node = 队首元素;

对node的处理，生成新node状态;

if (visited[node] == true)
continue;
if (node == target) {
输出答案;
return 0;
}
v[node] = true;
入队(node);
}
出队();
}

}

例题3 P1135 奇怪的电梯

P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1135


#include <iostream>  // 引入输入输出流    
#include <cstring>  // 引入C风格的字符串处理函数库，用于memset  
#include <queue>  // 引入队列容器  
using namespace std;  
  
const int N = 201;  // 定义常量N为201，表示图的最大节点数  
  
int n, a, b;  // n为图的节点数，a为起点，b为终点  
int k[N], vis[N], ans[N];  // k数组存储每个节点的关联值，vis数组标记节点是否被访问过，ans数组存储从起点到每个节点的最短路径长度  
  
// BFS函数，从节点a开始搜索  
void bfs(int a) {  
    queue<int> Q;  // 定义一个队列Q  
    Q.push(a);  // 将起点a加入队列  
    ans[a] = 0;  // 设置起点a到自身的距离为0  
  
    // 当队列不为空时继续循环  
    while (!Q.empty()) {  
        int u = Q.front();  // 取出队首元素  
        Q.pop();  // 弹出队首元素  
  
        // 如果当前节点是目标节点b，则结束搜索  
        if (u == b) {  
            break;  
        }  
        // 如果当前节点已经被访问过，则跳过  
        if (vis[u] == 1) {  
            continue;  
        }  
  
        vis[u] = 1;  // 标记当前节点为已访问  
  
        // 计算通过当前节点的关联值k[u]可以到达的两个节点v1和v2  
        int v1 = u + k[u];  
        // 如果v1是一个有效的节点且未被访问过，则将其加入队列，并更新ans[v1]  
        if (v1 >= 1 && v1 <= n && vis[v1] == 0) {  
            Q.push(v1);  
            ans[v1] = min(ans[v1], ans[u] + 1);  
        }  
  
        int v2 = u - k[u];  
        // 如果v2是一个有效的节点且未被访问过，则将其加入队列，并更新ans[v2]  
        if (v2 >= 1 && v2 <= n && vis[v2] == 0) {  
            Q.push(v2);  
            ans[v2] = min(ans[v2], ans[u] + 1);  
        }  
    }  
}  
  
int main() {  
    cin >> n >> a >> b;  // 输入节点数n，起点a和终点b  
  
    // 初始化ans数组为一个很大的数（表示无穷大）  
    memset(ans, 0x3f, sizeof(ans));  
  
    // 输入每个节点的关联值k[i]  
    for (int i = 1; i <= n; i++) {  
        cin >> k[i];  
    }  
  
    bfs(a);  // 从起点a开始BFS搜索  
  
    // 如果从a到b没有路径，则输出-1，否则输出最短路径长度  
    if (ans[b] == 1e9) {  
        cout << -1 << endl;  
    } else {  
        cout << ans[b] << endl;  
    }  
    return 0;  
}

四、BFS与DFS区别

bfs 遍历节点是先进先出，dfs遍历节点是先进后出；
bfs是按层次访问的，dfs 是按照一个路径一直访问到底，当前节点没有未访问的邻居节点时，然后回溯到上一个节点，不断的尝试，直到访问到目标节点或所有节点都已访问。
bfs 适用于求源点与目标节点距离最近的情况，例如：求最短路径。dfs 更适合于求解一个任意符合方案中的一个或者遍历所有情况，例如：全排列、拓扑排序、求到达某一点的任意一条路径。
————————————————

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/aliyonghang/article/details/128724989

五、练习题

1.DFS

P1036 [NOIP2002 普及组] 选数P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1036P1219 [USACO1.5] 八皇后 Checker Challenge

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1219P1644 跳马问题

P1644 跳马问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1644P1605 迷宫

P1605 迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1605

2.BFS

P1605 迷宫

P1605 迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1605P1443 马的遍历P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1443

以后可能陆陆续续会更新一点这几篇内容，先记录一下

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/145811