程序员经验分享-hwhale

最短路径：DFS、BFS 还是两者兼而有之？

2023-12-22

我知道仅 BFS 就可以在未加权图中找到最短路径，但我也在几个网站上读到，人们声称 BFS 或 DFS 可以做到这一点。我只是想确认这些可能是错误，并且只有 BFS 可以做到这一点（即使在快速进行谷歌搜索后我也不完全有信心）。如果我不正确，有人可以解释一下 DFS 如何给出最短路径吗？


DFS 不一定会产生无向图中的最短路径。 BFS 在这里是正确的选择。

举个例子，考虑一个通过取三角形的角并将它们连接起来而形成的图形。如果您尝试使用 DFS 找到从一个节点到另一个节点的最短路径，那么您将得到错误的答案，除非您沿着直接连接起始节点和目标节点的边进行操作。

正如 @nhahtdh 下面所指出的，DFS 有一个变体，称为迭代深化其中，您以最大深度 1、然后是 2、然后是 3 等运行 DFS，直到找到目标。这将始终找到最短路径，并且使用比 BFS 更少的内存。

希望这可以帮助！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

Graph

depthfirstsearch

breadthfirstsearch

最短路径：DFS、BFS 还是两者兼而有之？ 的相关文章

  • 运动结构，根据 2D 图像点对应关系重建 3D 点云

    Use case 物体绕其中心以不同的速度旋转 固定摄像机正在观察物体 给定 2D 图像点对应关系重建 3D 点云 当物体旋转时 相机可以看到它的不同部分 从而检测到不同的点和对应关系 Scene A N 张图片b N 1 图像对C N 1

  • 计算排列中“反转”的数量

    设 A 为一个大小的数组N 我们称之为几个索引 i j 一个 逆 如果i lt j and A i gt A j 我需要找到一种接收大小数组的算法N 具有唯一的数字 并返回时间的倒数数O n log n 您可以使用归并排序 http en

  • 匈牙利算法 - 系统分配

    我正在一个项目中实现匈牙利算法 我设法让它工作 直到所谓的步骤 4维基百科 http en wikipedia org wiki Hungarian algorithm Matrix 5Finterpretation 我确实设法让计算机创建

  • 使用 O(1) 辅助空间迭代二叉树

    是否可以在 O 1 辅助空间中迭代二叉树 不使用堆栈 队列等 或者这已被证明是不可能的 如果可以的话 怎样才能做到呢 编辑 我得到的关于如果有指向父节点的指针就可能实现这一点的响应很有趣 我不知道可以做到这一点 但取决于您如何看待它 这可以

  • Ruby 有哪些图形包/API？

    Similar Perl 有哪些图形包 API https stackoverflow com questions 460325 what graphing packages apis exist for perl 我正在对不同语言的在线图

  • 计算序列 1,3,8,22,60,164,448,1224... 的第 n 项？ [复制]

    这个问题在这里已经有答案了 可能的重复 我想以 Order 1 或 nlogn 的顺序生成序列 1 3 8 22 60 164 的第 n 项 https stackoverflow com questions 11301992 i want

  • 如何在 Perl 中生成数组的所有排列？

    生成所有内容的最佳 优雅 简单 高效 方式是什么 n perl 中数组的排列 例如 如果我有一个数组 arr 0 1 2 我想输出所有排列 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0 它可能应该是一个返回迭代器的

  • 递归最长递增子序列的记忆

    我为最长递增子序列提出了简单的以下递归解决方案 但是 您可以帮助将记忆包含到这个递归解决方案中吗 public int findLIS int a int maxSoFar int item int count if item a leng

  • 转置矩阵存储在一维数组中，无需使用额外的内存[重复]

    这个问题在这里已经有答案了 可能的重复 矩阵的就地转置 https stackoverflow com questions 9227747 in place transposition of a matrix 最近参加了技术笔试 通过以下问

  • LRU、FIFO、随机

    当出现页面错误或缓存未命中时 我们可以使用最近最少使用 LRU 先入先出 FIFO 或随机替换算法 我想知道 哪一个提供了最好的性能 也称为未来缓存丢失 页面错误最少的可能性 架构 Coldfire 处理器 没有愚蠢的问题 这句话非常适合这

  • 将 diff 转换为带有删除线的 Markdown？

    我想转换输出diff 在 Markdown 文件上 降价与

  • 如何找到权重为 1、0、-1 且成本精确为 0 的多维路径

    我得到了一个有向图 其中有 n 个节点和边 向量的权重 每个向量的长度为 m 为数字 1 0 1 我想找到从一个节点到另一个节点 我们可以多次访问节点 的任何路径 或者说这样的路径不存在 使其权重之和等于仅由零组成的向量 我正在考虑暴力回溯

  • 从邻接表计算图的入度

    我遇到了这个问题 其中需要根据邻接列表表示来计算图的每个节点的入度 for each u for each Adj i where i u if i u E in degree u 1 现在根据我的说法 它的时间复杂度应该是O V E V

  • cytoscape.js 页面上有多个实例

    我在同一网页上设置两个 cytoscape 实例时遇到问题 我有两个窗口变量 cy 和 cy2 用于不同的图形 它们是功能不同的图表 需要在页面的不同部分可用 我想知道如何正确设置 当我查看页面元素时 未显示的元素的底层画布的宽度和高度被

  • 缩小位图字体的算法

    这是后续这个问题 https stackoverflow com questions 4179414 low level c display text pixel by pixel 我正在开发一个低级 C 应用程序 我必须在其中绘制文本 我

  • 迭代格雷码更改位置的有效方法

    有多种迭代方式n 位格雷码 https en wikipedia org wiki Gray code Constructing an n bit Gray code 有些比其他更有效率 但是 我实际上并不需要格雷码 而是想迭代格雷码列表中

  • 如何用惰性传播实现线段树？

    我在互联网上搜索了有关线段树的实现的信息 但在惰性传播方面却一无所获 之前有一些关于堆栈溢出的问题 但它们专注于解决 SPOJ 的一些特定问题 虽然我认为这是用伪代码对线段树的最好解释 但我需要用惰性传播来实现它 我发现以下链接 除了上面的

  • 检测360度转弯算法

    我成功检测到手机绕轴的 0 360 度旋转 滚动 但现在我很难设计一种有效的算法来检测一整圈 我的工作但我认为不像我想要的那样优雅和有效的算法是 private boolean detectRoll private boolean chec

  • 将列表列表替换为“压缩”列表列表，同时保持顺序

    我有一个列表列表 如我所附的代码所示 如果有任何共同值 我想链接每个子列表 然后我想用列表的精简列表替换列表的列表 例子 如果我有一个清单 1 2 3 3 4 I want 1 2 3 4 如果我有 4 3 1 2 3 I want 4 3

  • 合并共享属性的节点

    EDITED 我真的需要 Networkx graph 专家的帮助 假设我有以下数据框 我想将这些数据框转换为图表 然后我想根据描述和优先级属性将两个图映射到相应的节点 df1 From description To priority 10

随机推荐

  • 在我的自定义 android 视图中添加自定义字符串属性

    我有一个从表布局派生的自定义视图 我需要声明 String 属性 Title 如下所示

  • Android 3.1 构建 gradle 4.4 配置项目 ':app' 时发生错误

    当我使用模拟器 api26 错误时 我没有使用 kotlin 因为不是导入 kotlin 而是构建 api gt 26 错误 gt kotlin KotlinNullPointerException 无错误消息 com android bu

  • MySQL大量“SET autocommit=0/1”查询

    我正在我们的系统上运行一些负载测试 我注意到正在执行大量 SET autocommit 0 和 SET autocommit 1 查询 1 分钟内大约有 25 000 个 我试图找出造成这种情况的原因以及如何消除它 我们使用以下技术 MyS

  • Qt Creator 将其设置保存在哪里？

    我想找到 Qt Creator 保存所有设置 文本编辑器首选项 语法突出显示等 的文件夹 以便我可以备份它们 有人知道他们在哪里吗 See QtCreator 快速浏览 http doc qt io qtcreator creator qu

  • 如何从XML获取Dataset中的多个表

    我正在读取数据集中的 XML 以下是我的 XML 结构 XML

  • Spring Boot - 从 webjar 覆盖索引页面

    在我的项目中 我使用 swagger ui 库 它在类路径的根目录中有 index html 文件 以这样的方式这个index html当我点击 root url 时 它会成为我的应用程序的起始页 但我想使用我的自定义 Groovy 模板i

  • 为什么需要内存对齐？

    我知道这个问题已经被问过一千次了 我已经阅读了每一个答案 但我仍然不明白 我的 RAM 模型可能存在一些根本性错误 使我无法理解任何答案 我从互联网上得到了所有这些小信息 但我就是无法将它们联系起来 以下是我认为到目前为止所知道的 以 IA

  • NS通知中心问题

    有没有办法知道一个对象是否已经注册为特定通知的观察者 在我的实现中 我必须动态添加和删除观察者 由于某种原因 存在一个随机问题 侦听器收到两次相同的通知 我知道我必须检查我的编码 但如果我知道这些信息 修复起来会更容易 谢谢 否 无法查询此

  • R、日期格式不一致

    我有一个日期变量 它最初来自 Excel 然而 它是如此异类 尽管在 Excel 中所有内容看起来都像 yyyy mm dd 但在 R 中读取时 变量看起来像 person 1 39257 person 2 2015 2 20 person

  • 如何将两个定点数相乘？

    我目前正在尝试找出如何以定点表示形式将两个数字相乘 假设我的数字表示如下 SIGN 2 0 2 1 2 2 2 14 就我而言 数量10 01000000000000 0 25 例如我会怎么做0 25x0 25 or 0 25x0 25 e

  • 如何将日期/时间字符串转换为不同的日期字符串？

    我将如何从日期转换此日期时间 摘自 2016 02 29 12 24 26 至 2016 年 2 月 29 日 到目前为止 这是我的代码 它返回一个 nil 值 let dateFormatter NSDateFormatter dateF

  • 数学问题：不同排列的数量

    这更像是一个数学问题 而不是编程问题 但我认为这里很多人都非常擅长数学 我的问题是 给定一个 9 x 9 网格 81 个单元格 其中必须包含数字 1 到 9 每个网格恰好 9 次 可以生成多少个不同的网格 数字的顺序并不重要 例如第一行可以

  • 如何计算 Firebase Analytics 原始数据中的会话和会话持续时间？

    如何计算会话持续时间在 Firebase 分析中raw data哪个与 BigQuery 相关联 我已使用以下博客通过对每个记录中嵌套的事件使用 flatten 命令来计算用户 但我想知道如何继续计算Session and 会话持续时间按国

  • CORS是双系统检查吗？

    阅读有关 CORS 的内容 https spring io understanding CORS https spring io understanding CORS 我有以下疑问 我认为在 CORS 中 请求在客户端被阻止 但在服务器中未

  • 如何配置 Travis-CI 以使用 Rails 应用程序的正确时区？

    在我的 application rb 中 我有 config time zone Pacific Time US Canada 这在开发 测试和生产服务器中可以正常工作 但是 当我推送到 Travis CI 时 它似乎已本地化为 UTC 例

  • 以编程方式获取 XPage 按钮的 clientId

    当我在表单上创建提交按钮时 会在 HTML 中生成以下内容 XSP attachEvent view id1 id2 id38 id55 view id1 id2 id38 button1 onclick null true 2 view

  • 二进制 XML 文件第 15 行：膨胀类片段时出错

    我有这个 xml 其中包含谷歌地图 v2

  • iPhone 应用程序上的 Xcode 链接器错误（仅在模拟器上）

    我收到此链接器错误 该错误不允许我进行编译 它只发生在模拟器上 关键点 仅发生在模拟器中 如同这个问题 https stackoverflow com questions 1456185 build error missing requir

  • 如何续订iPhone开发证书？

    我的开发证书已过期 正确的更新方法是什么 您是否撤销过期的证书并提交新的证书签名请求 是否必须重新创建配置文件 这样做有副作用吗 使用 Xcode 5 执行以下步骤 1 删除旧证书https developer apple com http

  • 最短路径：DFS、BFS 还是两者兼而有之？

    我知道仅 BFS 就可以在未加权图中找到最短路径 但我也在几个网站上读到 人们声称 BFS 或 DFS 可以做到这一点 我只是想确认这些可能是错误 并且只有 BFS 可以做到这一点 即使在快速进行谷歌搜索后我也不完全有信心 如果我不正确 有

热门标签