问题标签 [cycle-detection]

我想生成一个有向图，其中包含完全指定数量的循环以及它们各自的长度。例如，图表应包含：

• 这样的算法是否已经存在？如果不是，您将采取什么方法来解决这个问题？具体来说，给出以下参数：

  1. 顶点数（例如，15）
  2. 组件的数量（例如，2）
  3. 必须在图中的循环（例如，{3-cycle, 3-cycle, 5-cycle}）

• 我只发现了几种可以检测现有图中循环的算法（例如，Tarjan）。您认为还可以使用循环检测算法来生成具有特定循环数量的图形吗？

我研究了有向图中的循环检测算法的各种算法，如增量方式搜索、强连通分量、BFS、双向搜索等。现在我想模拟它并比较性能。每当我插入边缘时，我都会调用循环检测功能。

所以，我的问题是我应该考虑什么样的数据集。如果我考虑随机图，那么评估各种算法的标准应该是什么。一些随机图可能很大；但它们可能会导致几次迭代中的循环。如果有人可以建议如何去做这将是有帮助的。

另外，为了比较性能，删除循环然后再次继续插入是否有意义。一旦它终止，比较所有实现的执行时间？

有人可以提供一步一步的伪代码，使用 BFS 在有向/无向图中搜索循环吗？

它可以得到 O(|V|+|E|) 复杂度吗？

到目前为止，我只看到了 DFS 实现。

我有一个很大的 TinkerGraph（~80.000 个顶点，~160.000 个边），我需要使用Apache TinkerPop/Gremlin查询语言检测其中是否存在循环。如果有的话，我想获得其中一个循环的顶点。

有没有办法编写一个O(|V| + |E|)gremlin 查询来查找图中的循环路径？

我尝试使用此处和此处的查询，但它们太慢并且超时。我怀疑他们不是O(|V| + |E|)，但我仍在学习 TinkerPop，我无法评估 TinkerGraph 实现的内存/时间复杂度。

考虑以下链表：

上面的列表有一个循环如下：

在白板上绘制链表，我尝试手动解决不同的指针步骤，看看指针如何移动 -

(slow_pointer_increment, fast_pointer_increment)

因此，针对不同情况的指针如下：

前两对增量 - (1,2) 和 (2,3) 工作正常，但是当我使用对 (1,3) 时，算法似乎不适用于这对。是否有关于我们需要增加多少步骤才能使该算法成立的规则？

尽管我为较慢和较快的指针搜索了各种增量步骤，但到目前为止，我还没有找到一个相关的答案来说明为什么它不适用于此列表中的增量 (1,3)。

我正在从 C# 中的链表数据结构中解决一个程序，我需要检查给定的链表是 NULL 终止还是以循环结束。我想用不同的测试用例检查它，但不能将循环链表作为输入传递。

如何将循环链表作为输入传递？

来自hackerrank的问题会给你一个想法，我想要实现什么？

这是我实现图像中显示的链表的代码

鉴于以下重定向列表

在这里我们可以看到第一项“a”应该重定向到“b”。如果我们遵循列表，我们可以看到以下模式：

所以我们最终会得到一个循环引用，因为“a”最终会指向“d”而“d”指向“a”。

找到循环引用的最有效方法是什么？

我在 C# 中提出了以下算法

这会给我一个包含 4 个项目的列表，如下所示：

但我只对告诉用户类似的东西感兴趣

“嘿，你不能那样做，这将是一个循环引用，因为“a”指向“b”，“b”指向“c”，“d”指向“a”

那么，各位有什么建议吗？我确信存在一些其他（更好的）算法可以做到这一点...... :)

例如：

想知道他们使用什么样的结构来实现这一点，因为它没有直接编码到我刚刚做的事情中。似乎他们会做类似的事情：

然后它会得到它们，但不确定它是如何工作的。希望学习如何实现它。

在一个私人开源项目中，我遇到了以下问题：

有各种各样的任务要执行。其中一些任务将具有注释

• 它们必须在一项或多项特定的其他任务之后执行
• 它们必须在一项或多项特定的其他任务之前执行

我正在寻找一种简单的算法，该算法如何根据该信息构建有向图，然后可以将其用于循环检测并按照允许尊重所有这些条件的执行顺序的顺序执行所有任务任务。

问：构建这样一个图表的高效、好方法是什么？

谢谢您的帮助。

注意：很明显，我们将需要图中的两个额外节点：一个起始节点和一个结束节点。让我们将它们命名为 START 和 END。很明显，没有依赖关系的节点必须以 START -> A -> END 之类的结构结束。但是我不太清楚如何找到一个好方法来结束 START -> B -> C -> END 序列，因为 B 必须跟在 C 后面，而没有从 B 到 END 的边缘并且没有边缘从 START 到 C。

My CSV file has ~2.6 million records of transaction among different people. I am trying to make a graph from this file as: person having unique IDs as nodes and edges representing transaction between two people and want to fetch all possible cycles from the graph. I am trying to use networkx.simple_cycles(graph_name) to fetch all the cycles from this graph but getting this error:

My Python code looks like this:

My data looks something like this:

Can someone please help me with the error. Can there be some other way to find all the possible cycles from this graph?