程序员经验分享-hwhale

寻找有向或无向图中的最短循环

2024-04-15

我正在寻找一种算法来找到有向或无向图中的最短周期。

例如，对于节点 3，算法可能返回：

  • 周期1：3->10->11->7->8->3
  • 周期2：3->10->9->8->3

对于这些循环，最短的是循环 2，位于四个顶点。

我做了一些研究，发现了 Dijkstra 算法、DFS、BFS 和其他一些算法，但它们总是显示一条路径而不是一个循环。

PS：箭头并不重要。感谢您的帮助。


None

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

Algorithm

Graph

Cycle

shortestpath

寻找有向或无向图中的最短循环 的相关文章

  • 使用FFT算法计算

    给定在平面上的点 1 0 2 0 n 0 上发现的一组 n 个粒子电荷载流子 在 i 0 点发现的粒子电荷记为 Qi 作用在粒子上的力由以下公式给出 C is a Coulomb s constant 给出一个算法来计算 Fi 对于总复杂度

  • 使用C标准数学库精确计算标准正态分布的CDF

    标准 C 数学库不提供计算标准正态分布 CDF 的函数 normcdf 然而 它确实提供了密切相关的函数 误差函数 erf 和互补误差函数 erfc 计算 CDF 的最快方法通常是通过误差函数 使用预定义常量 M SQRT1 2 来表示 d

  • 如何高效地在屏幕上精确绘制N个点？

    这听起来是一个简单的问题 但我发现要获得良好的性能是非常棘手的 我提出的第一个算法是随机绘制点 从一组中检查是否已绘制 否则绘制 如果我们只绘制几个点 那么这种方法效果很好 但当我们接近填满屏幕时 速度会灾难性地减慢 我想出的最好的方法是构

  • 如何将无向图转换为 DAG？

    The 维基页面 http en wikipedia org wiki Directed acyclic graph Relation to other kinds of graphs says 任何无向图都可以通过为其顶点选择总顺序并将每

  • 图中的后边

    I m having a hard time understanding Tarjan s algorithm for articulation points I m currently following this tutorial he

  • 如何将一组重叠范围划分为不重叠范围？

    假设您有一组范围 0 100 一 0 75 b 95 150 c 120 130 d 显然 这些范围在某些点上重叠 您将如何剖析这些范围以生成不重叠范围的列表 同时保留与其原始范围相关的信息 在本例中为范围后面的字母 例如 运行算法后的上述

  • 找到一系列间隔的最有效分组

    我有一个应用程序 其中有一系列不重叠的固定宽度间隔 每个间隔都有一个给定的键 每个间隔具有相同的宽度 并且可以存在连续的间隔 本质上 我想以最小化单独间隔的数量的方式对间隔和键进行分组 这可以通过合并具有相同键的连续间隔或查找匹配间隔并将它

  • 最慢的计算复杂度（Big-O）

    在这些算法中 我知道 Alg1 是最快的 因为它是 n 平方的 接下来是 Alg4 因为它是 n 的立方 然后 Alg2 可能是最慢的 因为它是 2 n 这应该具有非常差的性能 然而Alg3和Alg5在我的阅读速度方面还没有遇到过 这两种算

  • 在 C++ 中通过引用传递 std 算法谓词

    我正在尝试从 a 中删除元素std list并保留已删除元素的一些统计信息 为此 我使用列表中的remove if 函数 并且我有一个谓词 我想使用这个谓词来收集统计数据 这是谓词的代码 class TestPredicate privat

  • Karasuba算法递归过多

    我正在尝试用 c 实现 Karasuba 乘法算法 但现在我只是想让它在 python 中工作 这是我的代码 def mult x y b m if max x y lt b return x y bm pow b m x0 x bm x1

  • Bokeh 中单独的节点和边缘悬停工具？

    我正在尝试为 Bokeh 中的节点和边缘获取单独的悬停工具提示 但未能使其正常工作 有人可以指出我做错了什么吗 我相信代码应该如下所示 from bokeh io import show output notebook from bokeh

  • 无需构建树即可预测霍夫曼压缩比

    我有一个二进制文件 我知道其中每个符号出现的次数 如果我要使用霍夫曼算法压缩它 我需要预测压缩文件的长度 我只对假设的输出长度感兴趣 而不对单个符号的代码感兴趣 因此构建霍夫曼树似乎是多余的 作为一个例子 我需要得到类似的东西 包含 4 个

  • 如何仅使用单个数组在 JavaScript 中模拟调用堆栈

    我正在看维基百科页面 https en wikipedia org wiki Call stack在调用堆栈上 并尝试理解这个图像 据我所知 哈哈 const memory memory 0 3 top of stack pointer m

  • 使用多级解决方案计算二维网格中的最近邻

    我有一个问题 在 x y 大小的网格中 我提供了一个点 并且我需要找到最近的邻居 在实践中 我试图在 pygame 中找到距离光标最近的点 该点跨越颜色距离阈值 计算如下 sqrt rgb1 0 rgb2 0 2 rgb1 1 rgb2 1

  • 如何有效地找到距给定点最远的点（从一组点中）？

    我正在寻找一种算法或数据结构来解决以下问题 给你一组点 S 然后你会得到另一个点形式的 Q 查询 对于每个查询 找到集合中距离给定点最远的点 集合中最多有 10 5 个点和 10 5 个查询 所有点的坐标都在 0 到 10 5 范围内 我想

  • d3力定向布局-链接距离优先

    在 d3 中使用力导向布局 如何使链接距离成为优先事项 同时仍然保持良好的图形布局 如果我指定动态链接距离 但保留默认费用 则我的图形距离会因费用函数而发生一些变形 并且不再是准确的距离 但是 如果我删除电荷 图表将如下所示 任何建议表示赞

  • 直接选择排序与交换选择排序

    有什么区别直接选择排序 vs 交换选择排序 今天我陷入了一场争论 我的教授在他的讲义中使用了这两个术语 维基百科和任何教科书或网站都会为您提供的选择排序就是他所说的 交换选择排序 我以前从未听说过 交换选择排序 这个术语 仅 选择排序 并且

  • 如何检查是否存在可能的路径？

    我正在开发一个基于 javascript 的实验性游戏 玩家必须在二维平铺地图上移动才能退出 请随意检查这个小提琴并演奏 http jsfiddle net moonlife 74vLd 我只是随机放置障碍物 但有时障碍物会挡住玩家和出口之

  • 子序列和

    给定一个整数数组 例如 1 2 3 1 查找是否存在总和为0并返回它 例如 1 2 3 or 2 3 1 检查每个子序列是O n 2 这效率太低了 有改进的想法吗 创建一个新数组 其中每个元素等于前一个元素加上该元素的总和 Input 1

  • 如何从迭代器推导连续内存

    不知何故 本土stl copy VC Dinkumware 上的算法表明它可以使用memcpy 可以轻松复制的数据 一个凡人能做到这一点吗 假设每个元素都是普通可复制的 random access iterator 是否意味着连续内存 标准

随机推荐

  • delphi读取xml元素

    我是 XML 新手 我们需要使用新的进行地理编码必应空间数据 API http msdn microsoft com en us library gg585131 aspx 我已经设法以 xml 格式从他们那里得到结果 我将如何阅读响应中的

  • rake db:test:prepare 中的 Rails 待迁移

    我已经跑了rake db migrate我所有的迁移都运行了 然而 当我尝试跑步时rake db test prepare我收到错误 You have 1 pending migrations 20130724211328 CreateGa

  • Extjs 4（下面有3.4的代码）下载从post请求返回的文件

    我看到了与此略有相关的问题 但没有一个能回答我的问题 我设置了 Ext Ajax request 如下 var paramsStringVar param1 1 param2 two param3 something param4 etc

  • 为什么接口 IOrderedEnumerable 在 T 中不是协变的？

    我正在查看 IOrderedEnumerable 的声明 令我惊讶的是它的 TElement 类型参数不是协变的 public interface IOrderedEnumerable

  • Java 输入问题 - 如何比较字符串[重复]

    这个问题在这里已经有答案了 这看起来很简单 但我已经被困在这里几个小时了 我有一个疑问 当你必须在Java中比较两个字符串时 如果我只是做这样的事情 String var1 hello String var2 hello 然后在另一个函数中

  • SwiftUI：ScrollView 拖动底部工作表

    我正在尝试创建一个 SwiftUI Scrollview 来拖动其容器 如下所示 https drive google com file d 1O92DgsVI1OjM1HEUXUwVywB8gcdShOP view usp sharing

  • PromQL if then 语句等效

    我有一个执行计数的简单 PromQL 查询 sum up container name my container environment name env 这是 Grafana 仪表板的一部分 允许从下拉菜单中选择 env 我想根据环境执行

  • SQL Server 分区查询

    当我运行查询时 select 100 50 它给我 2 很好 但是当我运行查询时 select 50 100 我原以为它会给我 0 5 但它却给了我 0 为什么 我怎样才能得到0 5 select 25 30 100 我预计它会给我 83

  • 获取Webbrowser Control中URL的原始源代码

    我有一个嵌入在 C Windows 应用程序中的浏览器控件 我想获取 url 包含的原始 HTML 不是渲染的 HTML 它可能已被 javascript 修改 与在 IE 中查看源代码中的内容相同 有什么建议么 WebBrowser Do

  • Python：使用 %x（区域设置）格式化的日期与预期不符

    我有一个日期时间对象 我想根据操作系统区域设置 例如在 Windows 7 区域和语言设置中指定 为其创建日期字符串 遵循Python的日期时间格式化文档 http docs python org library datetime html

  • Chrome Webview 中的 Service Worker 支持

    Android 版 chrome webview 是否支持 Service Worker 如果是 则支持哪个版本 尝试谷歌搜索 但没有找到正确的信息 As per 本公告 https chromereleases googleblog co

  • Opencv 函数只能以 C 代码方式调用，不能以 C++ 方式调用

    我对 Opencv 真的很陌生 按照说明下载并安装 Opencv 2 4 后 我开始编写我的第一个 Opencv 程序 这基本上是网络上教程的副本 include

  • 无法序列化泛型类型

    我正在尝试使用 protobuf net 序列化通用类型 但 protobuf net 说它无法序列化它 As in RuntimeTypeModel Default CanSerialize typeof MyGenericClass l

  • 在asp.net中通过javascript警报显示异常消息

    我试图通过 javascript 警报框显示异常消息 这是示例代码 public static void HandleException Page page Exception ex string message ex Message To

  • Spring中独立应用程序中的预定方法

    我有一个方法需要每天 07 00 执行 为此 我使用该方法创建了一个 bean 并用 Scheduled cron 0 0 7 在这个bean中我创建了一个mainfunction 它将初始化 spring 上下文 获取 bean 并调用方

  • 在 python 2.6 上加载 win32file.pyd 时出现问题

    即使是使用 win32file 的简单脚本 我也无法使 py2exe 正确打包 我不断收到以下错误消息 Traceback most recent call last File dependency checker py line 1 in

  • java中二维数组在内存中是如何表示的？

    我正在尝试使用键 值对实现数据结构 并正在研究数组实现 实现此目的的一种方法是为键和值声明单独的一维数组 private int keys new int N private int values new int N 但是 可以通过如下声明

  • 如何从正在侦听 dart 中某个流的函数返回字符串？

    我有一个名为 foo 的函数 它正在监听标准输出 我想要的是返回从标准输出获得的一些字符串 这是我的功能 dynamic foo process return process stdout transform UTF8 decoder li

  • 在 iPhone 上自定义 NSLog 函数

    我知道可以对 Objective C 中的选择器和方法进行方法混合 是否可以将 NSLog 等函数混合到我们的自定义函数中 我想在自定义函数中添加一些额外的功能和 NSLog EDIT 我最终使用了另一个在内部调用 NSLog 的函数 de

  • 寻找有向或无向图中的最短循环

    我正在寻找一种算法来找到有向或无向图中的最短周期 例如 对于节点 3 算法可能返回 周期1 3 gt 10 gt 11 gt 7 gt 8 gt 3 周期2 3 gt 10 gt 9 gt 8 gt 3 对于这些循环 最短的是循环 2 位于

热门标签