问题标签 [cyclic-graph]

我得到一个连接的加权图，权重为非负。我想将其转换为连接的非循环图，以使已删除边的权重总和最小化。输出将是删除的边缘。

我的想法：由于连接的无环图是一棵树，我可以简单地取最大n-1边，并删除所有其他边。但是，这可能并不总是正确的。它可能导致断开连接的图形。

然后，我想到了使用 dfs。我知道如何使用 dfs 检测图是否有循环，但我不知道如何检测所有涉及的边以及如何将其转换为无环图。任何帮助（代码/伪代码/算法）将不胜感激。谢谢...

我有一个通常是循环的有向图，我想找到节点和接收器之间的关系。对有向图的遍历似乎非常适合递归记忆，因为该图可以映射到每个节点的遍历结果并进行查询，类似于规范的斐波那契记忆。但是，我发现检测循环会阻碍记忆工作，因为循环检测需要知道路径，并且可能有许多路径通向同一个节点，因此映射到图形的结果似乎取决于路径参数。但是，当循环被忽略时，结果实际上是明确的，但我看不出有任何方法可以将其传达给编译器。

作为一个简单但说明性的示例，假设我想找到从图中的节点可到达的所有接收器。DFS 的朴素算法看起来像这样：

而试图为记忆而写这个显然会在尝试填写路径参数时遇到问题：

例如，在此图上的遍历中，我们可以看到从 A 到循环的路径有何不同，但如果节点 D 的结果被记忆，则遍历 D 只需执行一次：

我是否被迫使用显式表手动编写此备忘录？

我正在处理有根、有向、潜在循环图。图中的每个顶点都有一个标签，它可能是唯一的，也可能不是唯一的。边没有标签。该图有一个指定的根顶点，每个顶点都可以从该根顶点到达。从顶点出来的边的顺序是相关的。

出于我的目的，一个顶点等于另一个顶点，如果它们共享相同的标签，并且它们的出边也被认为是相等的（并且顺序相同）。如果两条边具有相同的方向并且其对应端的顶点相等，则它们相等。

由于上面的相等规则，一个图可以包含多个实际上相等的“部分”。例如，在下图中，有两个同构部分包含标签为 {1, 2, 3, 4} 的顶点。图的根是顶点 0。

我需要能够识别相同的部分，然后删除所有重复项，而不改变图形的“含义”（关于上面的相等规则）。使用上面的例子作为输入，我需要产生这个：

在多项式时间内是否有已知的方法可以做到这一点？

}

代码来源：来自 GeeksForGeeks 的“检测有向图中的循环”。

我试图修改此代码以使用此代码打印周期，但它似乎不适用于所有情况。例如，在边为 0->1,1->2,2->3,3->1 的图中，它将循环打印为 3 2 1 0 但实际循环为 3 2 1。两个循环起源于同一个顶点。

请帮助我更正代码以正确打印周期。

在线ide代码链接： https ://ide.geeksforgeeks.org/ujCcvL77ii

我正在尝试编写一个适用于循环图的谓词 isway(A, B)。我试图得到的预期结果是，两个节点之间是否存在路径。例如：如果我问 isway(a, f)，期望它回答是或否。下面是我的代码，但它永远不会起作用，并且总是给我 false 作为输出。

试图找到a 、 via中的所有循环。但是遇到了问题。directed graphDFS

问题

当2个节点之间有多个循环时，有时只能检测到最长的一个，较短的一个被跳过。

这是因为当访问一个节点时，我会跳过它，从而跳过较短的循环。但是，如果我不跳过访问过的节点，DFS 搜索将永远重复。

例子

图形：

1和之间有 2 个循环4：

• (A) 1 -> 2 -> 3 -> 4 -> 1
• (B) 1 -> 4 -> 1

无法检测到循环B，如果先检测到A，因为4访问过会被跳过，并且永远不会回到1。

当前的想法

• 一种可能的解决方案是从每个节点开始，即使它已经被访问过。但我想要一个更好的解决方案。
• 计算并记住路径的哈希，仅当存在相同的哈希时才跳过？这需要一些记忆，对吧？并且，仍然有可能 2 条具有相同哈希的不同路径导致相同的节点，它不能完全解决问题。

任何想法？

我试图在有向图中检测一个循环。
在提出解决它的逻辑时，我发现了一个简单的图遍历 eq. dfs 就足够了，因为在执行 dfs 时，我们只需要有一个条件来查看是否已经访问过任何节点。如果是这样，则必须有一个循环。

在查找解决方案以交叉检查我的逻辑时，我遇到了这个解决方案，它说在执行 dfs 并跟踪访问的节点时，您还需要跟踪递归堆栈中的节点并且节点已经在递归堆栈然后有一个循环 - 我不明白。
当我们可以简单地检查一个节点是否再次被访问并得出结论存在一个循环时，为什么我们需要跟踪递归堆栈中的节点？

所以我将这些值存储在一个数据框中，为了进一步计算，我想为每个单独的周期找到 max() 减去 min() 并将它们保存在一个变量中。信号总共有 10 个周期。

这张图片显示了我的信号，我想在其中提取每个单独周期的峰值和谷值。

我正在制作一个有向图类。我想查找是否有任何循环并相应地用它的路径更新一个向量。我的函数有时会起作用，但其他函数会在路径的最后一条边缘添加两倍。所以我想它需要整理一下。

示例：具有这些路径的图表

0->1, 0->2, 1->2, 2->3, 3->4, 4->0, 4->6, 1->5, 5->6

应该将向量设置为 [0 2 3 4] 或其他任何有效的值。

我试过的：

我想创建一个模块系统，您可以在其中以循环方式加载依赖项。原因是，在模型类之间的关系中，循环依赖无处不在，就像在 Ruby on Rails 中一样：

这通常在 Ruby on Rails 模型中的工作方式，至少，它首先加载所有模型，依赖项首先是一个符号或“字符串”。然后一个集中管理器获取所有这些对象并将字符串转换为相应的类，现在这些类都已定义。当你设置第一个类与其对应的类的关系时，其余的类仍然与字符串有关，而这个第一个类与类有关，因此有一个过渡期，其中一些模型完全解析为类，而其他的仍然是字符串，因为算法正在运行并且尚未完成。一旦所有的字符串都被解析为它们对应的类，算法就完成了。

我可以想象一个变得更加复杂的世界，创建的循环不是一对一的循环依赖，而是在它们之间有很多层，创建一个 5 节点循环之类的东西。甚至是模块之间存在来回依赖关系的地方，例如：

要解决此问题：

1. 加载所有文件 *.rb，将depends_on其视为字符串。现在我们在其相应的模块中定义了每个类，但使用depends_onas 字符串而不是所需的类。
2. 遍历文件并解析类。
3. 对于文件 1.rb，解析 X... 等。
4. X 依赖于 A，因此与 2/A 相关联。
5. X 也依赖于 B，因此与 2/B 相关联。
6. Y 取决于 B，因此与 2/B 相关联。
7. Z 取决于 Q，因此与 3/Q 相关联。
8. A 取决于 Y，因此与 1/Y 相关联。
9. B 取决于 Z，因此与 1/Z 相关联。
10. Q 取决于 X，因此与 1/X 相关联。
11. 完毕。

所以基本上，有两个“回合”。第一轮是加载所有文件，并初始化类。第二轮是将班级成员与相应的其他班级相关联。顺序无所谓。

但它可以变得更复杂吗？需要两轮以上来解决这种循环依赖？我不确定。以这样的为例：

在这种人为的情况下，您有：

1. A(file/1) 取决于A_P(file/2)，然后：
2. AA(file/1) 取决于A_P和AA_P，然后：
3. AA_P(file/2) 取决于B(file/1)，然后：
4. B(file/1) 取决于B_Q(file/2) 等....

也就是说，似乎正在发生一些奇怪的事情。我不确定，我的头开始打结。

1. 在完全解决类之前，您无法定义A正在扩展的类。在类完全解析之前，A_P您无法定义什么是类，这取决于被解析，这取决于被解析。ETC..AAAA_PBB_Q

是否有可能解决这种循环依赖？解决任意复杂循环依赖的一般算法是什么？这样，最终是所有循环依赖项都与实际值相关联，而不是字符串或其他表示实际值的符号。解决循环依赖的最终结果是每个引用都应该引用实际的对象。

它总是只是一个简单的两遍算法，首先加载基础对象，然后解析它们的依赖关系，将依赖关系的“字符串”转换为集合中的基础对象？

你能举出一个例子，它需要的不仅仅是简单的两遍算法吗？然后描述在这种情况下算法应该如何解决循环依赖？或者证明/解释如何确定只需要一个简单的两遍算法？

另一个例子可能是：

我想这也将是两次通过。