程序员经验分享-hwhale

图中的后边

2024-05-13

I'm having a hard time understanding Tarjan's algorithm for articulation points. I'm currently following this tutorial here: https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/ https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/. What I really can't see, and couldn't see in any other tutorial, is what exactly a "back edge" means. Considering the graph given there, I know 3-1 and 4-2 are back edges, but are 2-1, 3-2, and 4-3 back edges too? Thank you.enter image description here


...后边是将顶点连接到在其父级之前发现的顶点的边。

从你的source https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/.

这样想：当您在图上应用 DFS 时，您会修复算法选择的某些路径。现在在给定的情况下：0->1->2->3->4。正如在文章中提到的，源图包含边4-2 and 3-1。当 DFS 达到 3 时，它可以选择 1，但 1 已经在您的路径中，因此它是一个back edge因此，正如消息来源中提到的，这是一条可能的替代路径。

解决第二个问题：2-1、3-2 和 4-3 也是后边缘吗？对于不同的道路，他们可以是。假设你的 DFS 选择0->1->3->2->4 then 2-1 and 4-3是后边缘。

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

Algorithm

Graph

graphtheory

depthfirstsearch

tarjansalgorithm

图中的后边 的相关文章

  • 有人真正有效地实现了斐波那契堆吗？

    你们中有人曾经实施过斐波那契堆 http en wikipedia org wiki Fibonacci heap 几年前我就这样做了 但它比使用基于数组的 BinHeaps 慢了几个数量级 当时 我认为这是一个宝贵的教训 告诉我们研究并不

  • 绘图：仅保留最相关的数据

    为了节省带宽并且不用自己生成图片 图表 我计划使用 Google 的图表 API http code google com apis chart http code google com apis chart 它的工作原理是简单地发出一个

  • 用于图形操作的 Javascript 库

    有没有建议的 javascript 替代 pythonpygraph http code google com p python graph or NetworkX http networkx lanl gov 应该注意的是 可视化不是必需

  • Google 图表中的轴断了

    有什么方法可以在 Google 图表 api 上的垂直刻度中创建中断吗 我有几十个数据点 y 轴上的值都在 600 2000 左右 除了一个值几乎为 300 000 这使得所有较小的数据点几乎不可读 我需要表示所有这些数据 而对数刻度不是一

  • 在 Perl 中确定范围重叠的最快方法

    我有两组范围 每个范围都是一对整数 开始和结束 表示单个较大范围的某些子范围 两组范围的结构与此类似 当然 将替换为实际数字 a ranges a 1 gt start gt end gt a 2 gt start gt end gt a

  • 计算某个数的某次幂的模（该次幂的数字相当大）

    我想自己计算RSA算法 我需要计算某个数的某个幂的模数 问题是 在一定的功率下 这个数字可能会变得相当大 这就是我想要的 x pow n p q 如何有效地确定 x 如果您使用 NET 4 我建议您查看BigInteger http msd

  • 良好的线性代数包[关闭]

    Closed 此问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我正在为一个项目实现一些谱图算法 其中很大一部分是查找大型稀疏矩阵以及乘法矩阵的特征值和特征向量 我的问

  • Haskell：先进先出队列算法的复杂性

    这是我对 FIFO 队列的尝试 type Queue a a gt a empty Queue a empty id remove Int gt Queue a gt a Queue a remove n queue take n queu

  • 平均值大于或等于 k ​​的最长连续子数组

    考虑一个包含 N 个整数的数组 找到最长的连续子数组 使其元素的平均值大于 或等于 给定数字 k 显而易见的答案具有 O n 2 复杂度 我们可以做得更好吗 我们可以通过在 O n 时间内从所有值中减去 k 将这个问题简化为 sum gt

  • 找到经过大多数点的直线的最有效算法是什么？

    问题 N 个点在二维平面上给出 同一个点上最多有多少个点straight line The problem has O N2 solution go through each point and find the number of poi

  • 在数组中出现超过 n/3 次的数字

    我读过这个问题查找数组中最常见的条目 https stackoverflow com questions 278488 puzzle find the most common entry in an array 乔恩 斯基特的回答真是令人兴

  • 仅当 ggplot 中 y 轴的下限设置为 0 时才会出现图条[重复]

    这个问题在这里已经有答案了 我正在尝试创建一个条形图 当我将限制设置为 0 7 时 就会出现条形 但是 我希望下限为 1 而不是 0 当我将下限设置为 1 时 条形图不会出现 我收到以下错误消息 Removed 8 rows contain

  • 使用对象列表构建树

    我有一个带有属性 id 和parent id 的对象列表 我想建造一棵树来连接那些孩子和父母 1 个父对象可以有多个子对象 并且有一个对象将成为所有对象的祖先 实现该功能最快的算法是什么 我使用 C 作为编程语言 但其他语言也可以 像这样的

  • 获取大于某个数字的元素个数

    我正在尝试解决以下问题 数字被插入到容器中 每次插入数字时 我需要知道容器中有多少元素大于或等于当前插入的数字 我相信这两个操作都可以以对数复杂度完成 我的问题 C 库中有标准容器可以解决这个问题吗 我知道std multiset可以在对数

  • 如何随机打乱地图中的值？

    我有一个 std map 其中键和值均为整数 现在我想随机打乱地图 因此键随机指向不同的值 我尝试了 random shuffle 但它无法编译 请注意 我并没有尝试洗牌键 这对于地图来说没有意义 我正在尝试随机化这些值 我可以将这些值推入

  • 在skiena的书中给出的关于应用dfs在图中查找循环的代码中存在错误

    这是dfs的代码 bool processed MAXV 1 which vertices have been processed bool discovered MAXV 1 which vertices have been found

  • 在大文件中查找重复字符串

    一个文件包含大量 例如100亿 字符串 您需要查找重复的字符串 您有 N 个可用系统 您将如何找到重复项 埃里克森的答案可能是提出这个问题的人所期望的 您可以将 N 台机器中的每台机器用作哈希表中的一个存储桶 对于每个字符串 按顺序说出字符

  • 如何解决素数函数的大O表示法？

    我正在尝试理解 Big O 表示法 很抱歉 如果我问的问题太明显了 但我似乎无法理解这一点 我有以下 C 代码函数 我正在尝试为其计算 Big O 表示法 for i 2 i lt 100 i for j 2 j lt i j j if i

  • 快速算法可以快速找到一组范围中某个数字所属的范围？

    场景 我有几个数字范围 这些范围不重叠 由于它们不重叠 逻辑结果是任何时候任何数字都不能属于多个范围 每个范围都是连续的 单个范围内没有空洞 因此范围 8 到 16 将真正包含 8 到 16 之间的所有数字 但两个范围之间可能存在空洞 例如

  • 如何在python中访问矩阵每个元素的相邻单元格？

    这里 如果两个单元共享边界 则它们被认为是相邻的 例如 A 5 6 4 2 1 3 7 9 8 这里 索引 0 0 的相邻元素位于索引 0 1 和 1 0 处 索引 1 1 的相邻元素位于索引 0 1 1 0 2 1 处 和 1 2 假设你

随机推荐

热门标签