搜索与图论第二期 BFS

这篇具有很好参考价值的文章主要介绍了搜索与图论第二期 BFS。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

BFS跟DFS同样重要,也一定要熟练的掌握!!!

一、BFS的基本内容

BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。
如果所有节点均被访问,则算法中止。
BFS同样属于盲目搜索。
一般用队列数据结构来辅助实现BFS算法。

算法步骤:

1首先将根节点放入队列中。
2从队列中取出第一个节点,并检验它是否为目标。如果找到目标,则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。
3若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
重复步骤2。

模板:

 
记录head节点为已经访问;
q.push(head);
 
while (q.empty()) { //当队列q不为空,则继续遍历
    xxx tmp = q.front(); //取出队列q的首数据
    q.pop();
 
    //判断 tmp 节点是否为终点
    if (tmp为目标状态) {
        输出记录,结束遍历
    } else {
        按照题目要求,生成下一步节点next
        if (判断 next 的合法性) {
            记录next节点为已经访问;
            q.push(next);//将合法节点推入到队列中
        }
    }
}

二、典型例题

1.八数码:

搜索与图论第二期 BFS,搜索与图论,宽度优先,算法文章来源地址https://www.toymoban.com/news/detail-810992.html

AC代码:

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>//哈希表存所有距离
#include <cstring>
using namespace std;

int bfs(string start) {
	string end = "12345678x";//终点
	queue<string>q;//宽搜队列
	unordered_map<string, int>d;//距离数组,到开始的距离
	q.push(start);//先把start放队列里去
	d[start] = 0;
	int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//上下左右四个数相对于x的位置
	while (q.size()) {//宽搜过程
		auto t = q.front();
		q.pop();
		int distance = d[t];
		if (t == end)//t是终点
			return distance;//返回距离

		//状态转移
		int k = t.find('x');//k来存储x的位置,find返回x的下标
		int x = k / 3, y = k % 3; //把一维数组的下标转化成二维数组的下标
		for (int i = 0; i < 4; i++) {
//x,y是当前'x'的位置,a,b是移动一次之后'x'的位置
			int a = x + dx[i], b = y + dy[i];
			if (a >= 0 && a < 3 && b >= 0 && b < 3) {//a,b都没有出界
				//二维数组的下标a,b对应到一维数组的下标a*3+b
				swap(t[k], t[a * 3 + b]);//状态更新
				//如果更新完之后的t之前没有搜过的话,就说明找到了一个新的状态
				if (!d.count(t)) {
					d[t] = distance + 1;//新的状态的距离更新
					q.push(t);//把新的状态加到队列里
				}
				swap(t[k], t[a * 3 + b]);//恢复状态
			}
		}
	}
	return -1;//如果在宽搜的过程中没有找到,终点返回-1
}

int main() {
	string start;//start存初始状态
	for (int i = 0; i < 9; i++) {
		char c;
		cin >> c;
		start += c;
	}
	cout << bfs(start) << endl;
	return 0;
}

总结

BFS十分重要希望我们都能够熟练的掌握,感谢大家的观看!!!

到了这里,关于搜索与图论第二期 BFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 搜索与图论第六期 最短路问题

    Dijkstra算法是一种著名的图算法,主要用于求解有权图中的单源最短路径问题。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉(Edsger Wybe Dijkstra)在1956年首次提出。Dijkstra算法的核心思想是通过以下步骤逐步构建最短路径树: 初始化:创建一个空白的最短路径字典,其中每

    2024年02月20日
    浏览(42)
  • C#,图论与图算法,图(Graph)广度优先遍历(BFS,Breadth First Search)算法与源代码

    深度优先算法(DFS,Deep First Search)与 宽度优先遍历(BFS,Breadth First Search) 是树、图数据结构的基础性、标准性的遍历算法。 深度优先搜索(DFS)是一种用于搜索图形或树数据结构的算法。该算法从树的根(顶部)节点开始,尽可能沿着给定的分支(路径)向下,然后回溯

    2024年03月23日
    浏览(40)
  • BFS算法(宽度优先搜索)超强解析 BFS迷宫问题图文详解 DFS与BFS的区别

      前情回顾:DFS练习-迷宫(最短路径)问题详解 一波三折 图片+文字 以及你需要会的基础:手搓数据结构之队列queue C/C++语言版(BFS算法预备知识) 广度优先搜索(Breadth First Search)简称广搜或者 BFS, 是遍历图存储结构的一种算法 。 BFS的原理是 “逐层扩散” ,从起点出发

    2024年02月22日
    浏览(48)
  • 图论算法|深度优先搜索理论基础|797.所有可能的路径|广度优先搜索BFS理论基础|200. 岛屿数量

    dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,在换方向(换方向的过程就涉及到了回溯)。 递归和回溯是相辅相成的 https://leetcode.cn/problems/all-paths-from-source-to-target/ 有向无环图(DAG): 有环无向图是指在图中存在至少一个环(Cycle)的无向图。环是

    2024年02月15日
    浏览(60)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(52)
  • 【图论--搜索篇】宽度优先搜索,广度优先搜索

    今日语录: 成功是一种心态,如果你相信自己能做到,那你已经迈出成功的第一步。

    2024年01月24日
    浏览(47)
  • 算法:BFS宽度优先遍历

    本篇总结的是BFS算法,BFS算法相比起DFS算法来说还是比较简单的 这里提供一种双端队列的做法,也可以在合适的层数逆序

    2024年02月21日
    浏览(57)
  • 算法-双指针、BFS与图论-1101. 献给阿尔吉侬的花束

    题目 思路 BFS可以搜环,有环也没有关系,如果有解:一定可以找到一条最小步数的合法的路径 Python中 collections模块的详细用法介绍_python collections-CSDN博客 引用自上述文章: append(x):添加 x 到右端。 appendleft(x):添加 x 到左端。 clear():移除所有元素,使其长度为0. copy():创

    2024年03月14日
    浏览(51)
  • 【算法】复习搜索与图论

    🍎 博客主页:🌙@披星戴月的贾维斯 🍎 欢迎关注:👍点赞🍃收藏🔥留言 🍇系列专栏:🌙 蓝桥杯 🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!🌙 🍉一起加油,去追寻、去成为更好的自己!

    2024年02月05日
    浏览(46)
  • 搜索与图论 - 搜索与图在算法中的应用【中】

    目录 迪杰斯特拉算法Dijkstra  Dijkstra求最短路 I Dijkstra求最短路 II 贝尔曼-福特算法 bellman-ford 有边数限制的最短路 SPFA算法 spfa求最短路  spfa判断负环 Floyd Floyd求最短路   该算法不能存在负权边 思路: 初始化距离数组, dist[1] = 0, dist[i] = inf; for n次循环 每次循环确定一个min加

    2023年04月08日
    浏览(82)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包