搜索结果
查询Tags标签： bfs，共有 162条记录-
广度优先搜索— —提高Ⅲ（BFS优化）
双向广搜 所谓双向广搜，就是初始结点向目标结点和目标结点向初始结点同时扩展，直至在两个扩展方向上出现同一个结点，搜索结束。它适用的问题是，扩展结点较多，而目标结点又处在深沉，如果采用单纯的广搜解题，搜索量巨大，搜索速度慢是可想而知的，同时往往也会出现内…
2022/2/11 23:46:54 人评论 次浏览 -
广度优先搜索— —提高Ⅱ
多源BFS 多源BFS，即同时存在多个起点，然后要求计算出图中任意一个点距离所有起点的最短距离，即图中任意点到每个起点的距离的最小值。 和一般的BFS的区别在于存在多个起点，而我们可以对所有的起点建立一个虚拟超级起点S，S与所有给定的起点一步相邻。设S到点A的最短距…
2022/2/11 23:46:52 人评论 次浏览 -
DFS与BFS算法
深度优先遍历简称DFS（Depth First Search），广度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种方式。下面分别介绍两种基本的搜索算法。 理论介绍 深度优先遍历DFS DFS属于图算法的一种，是针对图和树的遍历算法。深度优先搜索是图论中的经…
2022/2/6 9:12:39 人评论 次浏览 -
2022年三国杀华容道程序+BFS算法
2022年三国杀华容道程序+BFS算法程序代码如下 #include <bits/stdc++.h> using namespace std;set< vector<int> > vis;struct Move {vector<int> now;int id, dire; // dire 0 表示往上或往左 1 表示往下或往右 };map< vector<int>, Mo…
2022/2/1 14:58:00 人评论 次浏览 -
A*算法
A*寻路算法 引入假设你身处一座迷宫，要从起点穿过障碍到达终点，像上图一样，想要快速找到一条最短路径该如何做呢？ DFS？显然太耗时间。BFS？有太多点不必遍历。 所以，我们可以引入A*算法来解决这一问题。 概述A*（A-Star)算法是一种静态路网中求解最短路径最有效的直…
2022/1/25 17:04:53 人评论 次浏览 -
6.4.2 用BFS求最短路
前面的篇幅占了太多，再次新开一章，讲述BFS求最短路的问题 注意此时DFS就没有BFS好用了，因为DFS更适合求全部解，而BFS适合求最优解 这边再次提醒拓扑变换的思想在图形辨认中的重要作用，需要找寻不同图形在进行拓扑变换时候的不变性 假设有一个网格迷宫，由n行m列的单元…
2022/1/24 6:06:04 人评论 次浏览 -
【力扣】104. 二叉树的最大深度（DFS、BFS）
题目： 104. 二叉树的最大深度 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例： 给定二叉树 [3,9,20,null,null,15,7]，3/ \9 20/ \15 7 返回它的最大深度 3 。方法一：深度优…
2022/1/22 23:08:54 人评论 次浏览 -
Python队列与广度优先搜索(BFS)及其相关题目（更新中）
队列与广度优先搜索及其相关题目 1. 队列基础知识1.1 队列简介1.2 队列的顺序存储与链式存储1.2.1 队列的基本操作1.2.2 队列的顺序实现（List）1.2.3 循环队列的提出及其实现方法1.2.4 队列的链式存储实现 1.3 队列的应用 2. 广度优先搜索2.1 简介2.2 基于队列的广度优先…
2022/1/22 21:04:54 人评论 次浏览 -
LeetCode752. 打开转盘锁(BFS)
752. 打开转盘锁 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 。每个拨轮可以自由旋转：例如把 9 变为 0，0 变为 9 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 0000 ，一个代表四个拨轮的数字的字符串。 列…
2022/1/20 6:47:25 人评论 次浏览 -
LeetCode752. 打开转盘锁(BFS)
752. 打开转盘锁 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 。每个拨轮可以自由旋转：例如把 9 变为 0，0 变为 9 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 0000 ，一个代表四个拨轮的数字的字符串。 列…
2022/1/20 6:47:25 人评论 次浏览 -
Leetcode 多维度dp+优先队列+bfs
LC 1263. 推箱子 题目：推箱子中箱子的最少移动步数，人的次数不算 方法一：优先队列+BFS Node{步数，人x，人y，箱子x，箱子y}，优先队列按步数从小到大排序，每次取最小的出来更新（相当于Dijkstra变形），vis记录节点是否访问。 也可以完全用dis数据，记录达到某状态的…
2022/1/13 6:07:24 人评论 次浏览 -
Leetcode 多维度dp+优先队列+bfs
LC 1263. 推箱子 题目：推箱子中箱子的最少移动步数，人的次数不算 方法一：优先队列+BFS Node{步数，人x，人y，箱子x，箱子y}，优先队列按步数从小到大排序，每次取最小的出来更新（相当于Dijkstra变形），vis记录节点是否访问。 也可以完全用dis数据，记录达到某状态的…
2022/1/13 6:07:24 人评论 次浏览 -
力扣1036.逃离大迷宫(Python题解)
题目网址： https://leetcode-cn.com/problems/escape-a-large-maze/submissions/ 题目解析： 迷宫题目应该利用bfs进行解答，但是这道题目需要一点优化，给出的迷宫最大可到[1e6, 1e6]， 数目庞大，如果直接进行遍历那么肯定会超时，但是我们可以巧妙地利用这个障碍，如果…
2022/1/11 22:06:03 人评论 次浏览 -
力扣1036.逃离大迷宫(Python题解)
题目网址： https://leetcode-cn.com/problems/escape-a-large-maze/submissions/ 题目解析： 迷宫题目应该利用bfs进行解答，但是这道题目需要一点优化，给出的迷宫最大可到[1e6, 1e6]， 数目庞大，如果直接进行遍历那么肯定会超时，但是我们可以巧妙地利用这个障碍，如果…
2022/1/11 22:06:03 人评论 次浏览 -
BFS宽度优先搜索
BFS是一层一层往外搜，边权为1； 以题目为例：最经典的走迷宫问题 由于每个点只会经过一次，且根据BFS的特性，所以得出到每个点的步数都是最短的。这里就可以直接套用模板 1.将起点入队，标记 2.用while循环，当队列不为空时，取出对头，扩展对头，标记 3.将对头出队步骤…
2022/1/6 23:36:46 人评论 次浏览
