程序员经验分享-hwhale

DAG 中两个节点之间的路径数

2024-04-27

我想找到 DAG 中两个节点之间的路径数。 O(V^2) 和 O(V+E) 是可以接受的。

O(V+E) 提醒我以某种方式使用 BFS 或 DFS，但我不知道如何使用。 有人可以帮忙吗？


对 DAG 进行拓扑排序，然后从目标向后扫描顶点到源。对于每个顶点v，记录来自的路径数v到目标。当你到达源头时，该计数的值就是答案。那是O(V+E).

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

Algorithm

graphtheory

directedacyclicgraphs

DAG 中两个节点之间的路径数 的相关文章

  • 一种递归算法，用于在数组中查找总和为给定整数的两个整数

    我需要一个算法来确定数组是否包含两个总和为给定整数的元素 数组已排序 该算法应该是递归的并且运行时间为 O n 递归步骤应该基于总和 这意味着该方法传递总和并根据最终结果返回 true 或 false 如果找到两个元素 返回 true 否则

  • 什么是确定性快速排序？

    我一直在阅读有关快速排序的内容 发现有时它被称为 确定性快速排序 这是普通快速排序的替代版本吗 普通快速排序和确定性快速排序有什么区别 普通 确定性 快速排序在特定数据集上的行为可能非常差 例如 选择第一个未排序元素的实现在已排序数据上的时

  • 优化 HTML 属性压缩顺序

    我在某处读到 按一定顺序组织 HTML 属性可以提高 HTML 文档的压缩率 我想我是从 Google 或 Yahoo 推荐的更快网站上读到这篇文章的 如果我没记错的话 建议是将最常见的属性放在第一位 例如id等 然后将其余的按字母顺序排列

  • 为什么《破解编码面试》这个例子的时间复杂度是O(k c^k)？

    该问题来自 破解编码面试 第 6 版 问题 V1 11 以下代码打印长度为 k 的所有字符串 其中字符 是按排序顺序排列的 它通过生成所有长度的字符串来做到这一点 k 然后检查每个是否已排序 什么是运行时间 package QVI 11 P

  • 数组中最远的相等元素

    假设你有一个未排序的数组 你如何找到两个相等的元素 使它们成为数组中最远的元素 例如8 7 3 4 7 5 3 9 3 7 9 0ans 将是7 9 7 1 8 我想到了以下几点 initialise max 0 using hashing

  • 用于计算三角函数、对数或类似函数的算法。仅限加减法

    我正在修复 Ascota 170 古董机械可编程计算机 它已经开始工作了 现在我正在寻找一种算法来展示其功能 例如计算三角或对数表 或类似的东西 不幸的是 从数学运算来看 计算机只能进行整数的加减法 从 1E12到1E12的55个寄存器 甚

  • 如何在单向链表（一次遍历中）中从尾部获取第 n 个节点？

    所以我在一次考试中得到了这个问题 如何从单链表的尾部获取第 n 个节点 每个节点都有一个值和一个下一个 指向下一个值的指针 我们得到这个 getNodeFromTail Node head int x 所以我的做法是通过遍历一次来求出列表的

  • 如何检查无向图是否有奇数环

    我试图找到一个 O V E 时间算法来检查是否已连接 无向图有或没有奇数环 我正在考虑对图进行广度优先搜索 并尝试将顶点标记为黑色和白色 以便没有两个标记为相同颜色的顶点相邻 是否有任何已知的更简洁的算法可以在线性时间内解决这个问题 你的方

  • 查找文本中所有关键字的有效算法

    我有很多字符串 其中包含许多不同拼写的文本 我通过搜索关键字来标记这些字符串 如果找到关键字 我将使用该关键字的关联文本 假设搜索字符串可以包含文本 schw schwa 和 施瓦茨 我有三个关键字 全部解析为文本 schwarz 现在我正

  • 有效地合并两个数组 - 一个已排序，另一个未排序

    我正在解决一个问题 该问题有一个由 n 个元素组成的排序数组 后跟一个未排序的长度数组 O logn O 平方 n 如何最有效地对整个列表进行排序 在上述两种情况下我应该使用哪种排序 由于将单个元素插入数组并保持其排序是O n 你不可能变得

  • 定点数学比浮点运算快吗？

    多年前 即 20 世纪 90 年代初期 我构建了图形软件包 该软件包基于定点算术和预先计算的 cos sin 表格以及使用牛顿近似方法进行 sqrt 和对数近似的缩放方程来优化计算 这些先进技术似乎已经成为图形和内置数学处理器的一部分 大约

  • Python Pandas：沿一列比较两个数据帧，并返回另一个数据帧中两个数据帧的行内容

    我正在处理两个 csv 文件并作为数据框 df1 和 df2 导入 df1 有 50000 行 df2 有 150000 行 我想将 df2 的 时间 与 df1 求时间差并返回所有列的值 对应相似的行 保存在df3中 时间同步 例如 35

  • 在任意时间范围内找到最佳日/月/年间隔的算法？

    如果您有时间表 请说 March 19 2009 July 15 2011 是否有一种算法可以将该时间范围分解为 March 19 2009 March 31 2009 complete days April 1 2009 December

  • “包含字符串”的快速索引

    在我的应用程序中 我有多达数百万个短字符串 大部分短于 32 个字符 我想实现一个带有附加列表的搜索框 该列表仅包含包含在搜索框中输入的整个字符串的元素 如何预先建立索引来快速找到此类字符串 所有排序的 STL 容器都会检查整个字符串 对于

  • Java 2d 游戏中的路径查找？

    本质上它是我正在开发的一款吃豆人克隆游戏 我有一个 Enemy 类 并创建了该类的 4 个实例 它们都代表游戏的 4 个幽灵 所有幽灵都会在屏幕的随机区域启动 然后它们必须朝着吃豆人角色前进 当玩家控制吃豆人并移动它时 他们应该跟随它并尽可

  • 为什么这个算法的Big-O复杂度是O(n^2)？

    我知道这个算法的大O复杂度是O n 2 但我不明白为什么 int sum 0 int i 1 j n n while i lt j sum 即使我们设定了j n n一开始 我们在每次迭代期间递增 i 并递减 j 因此最终的迭代次数不应该比n

  • 颜色逻辑算法

    我们正在构建一个体育应用程序 并希望将团队颜色融入到应用程序的各个部分 现在 每个团队都可以使用几种不同的颜色来表示 我想做的是执行检查以验证两个团队颜色是否在彼此一定的范围内 这样我就不会显示两个相似的颜色 因此 如果团队 1 的主要团队

  • 删除近排序数组中未排序/离群元素

    给定一个像这样的数组 15 14 12 3 10 4 2 1 我如何确定哪些元素乱序并删除它们 在本例中为数字 3 我不想对列表进行排序 而是检测异常值并将其删除 另一个例子 13 12 4 9 8 6 7 3 2 我希望能够删除 4 和

  • Python：如何将列表列表的元素转换为无向图？

    我有一个程序 可以检索 PubMed 出版物列表 并希望构建一个共同作者图 这意味着对于每篇文章 我想将每个作者 如果尚未存在 添加为顶点 并添加无向边 或增加每个合著者之间的权重 我设法编写了第一个程序 该程序检索每个出版物的作者列表 并

  • Prolog，确定图是否是非循环的

    我需要定义一个谓词 acycling 1 它将一个图作为输入并确定该图是否是非循环的 所以根据我的理解 graph1 a b graph1 b c graph1 c a 将返回 no 和 graph2 a b graph2 b c 将返回是

随机推荐

热门标签