问题标签 [cyclic-graph]

我们如何检测有向图是否是循环的？我想使用广度优先搜索，但我不确定。有任何想法吗？

我已经解决了这里发布的大多数问题，除了最长的路径之一。我已经阅读了关于最长路径的 Wikipedia 文章，如果图表是非循环的，这似乎很容易出现问题，而我的不是。

那我该如何解决这个问题呢？蛮力，通过检查所有可能的路径？我什至如何开始这样做？

我知道它会在大约 18000 的图表上花费很多。但无论如何我只想开发它，因为它是项目所必需的，我将对其进行测试并以较小比例的图表展示给讲师，其中执行时间仅为一两秒。

至少我完成了所有需要的任务，并且我有一个运行的概念证明它可以工作，但是在循环图上没有更好的方法。但我不知道从哪里开始检查所有这些路径......

我正在为一个班级写一个 Settlers of Catan 克隆。额外的信用功能之一是自动确定哪个玩家拥有最长的道路。我已经考虑过了，似乎深度优先搜索的一些细微变化可能会起作用，但我无法弄清楚如何处理循环检测，如何处理玩家的两个初始道路网络的加入，和其他一些细节。我怎么能在算法上做到这一点？

对于不熟悉这个游戏的人，我会尽量简洁抽象地描述这个问题：我需要在一个无向循环图中找到最长的可能路径。

假设我有这个简单的类：

生成对的循环图是不可能的。

你将如何创建一个类似的类，它仍然是不可变的，但可以以某种方式用于生成循环图？

I have a cyclic graph-like structure that is represented by Node objects. A Node is either a scalar value (leaf) or a list of n>=1 Nodes (inner node).

Because of the possible circular references, I cannot simply use a recursive HashCode() function, that combines the HashCode() of all child nodes: It would end up in an infinite recursion.

While the HashCode() part seems at least to be doable by flagging and ignoring already visited nodes, I'm having some troubles to think of a working and efficient algorithm for Equals().

To my surprise I did not find any useful information about this, but I'm sure many smart people have thought about good ways to solve these problems...right?

Example (python):

A is equal to B, because it represents exactly the same graph.

BTW. This question is not targeted to any specific language, but implementing hashCode() and equals() for the described Node object in Java would be a good practical example.

我已经搜索并找到了有关此主题的一些信息，但答案要么令人困惑，要么不适用。

我有这样的事情：

现在，我想说的是，加载一个文件，解析它并从中填充这个数据结构。它是不可变的和循环的，人们怎么可能这样做呢？

另外，假设我确实填充了这个数据结构，现在我想修改它，比如更改 rootThing.refs(3).name，如何做到这一点？

感谢您在此处发布的想法。在这一点上，我在想，如果一个人真的想要这样的持久数据结构，那么跳出框框思考并考虑客户端代码需要提出哪些问题。因此，与其考虑对象和字段，不如考虑查询、索引等。首先，我在考虑： 是否有双向多图持久数据结构？

令 G 为包含循环的未加权有向图。我正在寻找一种算法，它可以找到/创建所有无环图 G'，由 G 中的所有顶点和 G 的边的子集组成，小到足以使 G' 无环。

更正式：所需的算法消耗 G 并创建一组无环图 S，其中 S 中的每个图 G' 满足以下属性：

1. G'包含G的所有顶点。
2. G' 包含 G 的边的子集，因此 G' 是非循环的。
3. G'的边数最大化。这意味着：不存在满足属性 1 和 2 的 G''，使得 G'' 包含比 G' 更多的边，并且 G'' 是无环的。

背景：原始图 G 对元素之间的成对排序进行建模。由于图中的循环，这不能被用作对所有元素的排序。因此，最大无环图 G' 应该对该排序进行尽可能最佳的近似建模，尽量尊重成对排序关系。

在一种简单的方法中，可以删除所有可能的边组合，并在每次删除后检查非循环性。在这种情况下，存在一个强烈分支的变化树，这意味着时间和空间复杂度不好。

注意：问题可能与生成树有关，您可以将 G' 图定义为一种有向生成树。但请记住，在我的场景中，G' 中的一对边可能具有相同的起始顶点或相同的结束顶点。这与文献中使用的一些有向生成树的定义相冲突。

编辑：添加了与生成树相关的直观描述、背景信息和注释。

给定一个有向循环图，我如何获得代表输入图的各种 DAG/树？实际上，我想从给定的电路（有向和循环）图中提取各种树。

我有一个使用dosyncand创建的循环图ref-set。当我将它传递给我时，println我得到了java.lang.StackOverflowError我所期望的 a，因为它实际上是在尝试打印一个无限嵌套的结构。

我发现，如果我这样做(str my-ref)，它会创建一些看起来像vertex@23f7d873但实际上并没有尝试遍历结构并将所有内容打印出来的东西，所以这从直接意义上解决了问题，但只有当我非常小心我的内容时才有帮助m 打印到屏幕上。我希望能够调用(println my-graph)让它打印ref为某种类型的自定义文本（可能涉及str），以及其他非参考的东西。

目前我有一个自定义打印功能，它自己打印结构的每个元素并完全跳过打印ref. （事实证明，看vertex@23f7d873实际上并不是很有用）。这使用起来很尴尬，并且极大地阻碍了在 REPL 中对内容进行随意检查，并且还阻止了 Emacs 检查员在我处于swank.core/break调试状态时查看内容。

一个细节是ref实际上是 a 中的一个值defstruct，它还包含我试图正常打印的一些其他内容。

所以我想知道我应该走哪条路。我看到这些选项：

1. 找出协议extend-type并将其应用于CharSequencemy defstructed 结构，以便在遇到 a 时ref它可以正常工作。这仍然需要对结构进行逐个字段的检查，并在涉及到 时需要特殊情况ref，但至少它将问题定位到结构而不是包含该结构的任何东西。
2. 找出CharSequence在遇到ref. 这允许更本地化的行为，并允许我在 REPL 上查看循环引用，即使它不在结构内。这是我的首选。
3. 弄清楚如何做一些toString我认为在我做的时候在某种程度上被调用的事情println。我对这个选项最无知。对其他的也很无知，但我一直在阅读Joy of Clojure，现在我都受到了启发。

同样，此解决方案应适用于print和pprint其他任何在尝试打印循环引用时通常会出错的东西。我应该采用什么策略？

非常感谢您的任何意见。

我需要在 Prolog 中使用循环构造有向图（在运行时），但我不确定如何表示它。我的要求是我需要在恒定时间内从一个顶点到达他的邻居。

是否可以将其表示为一棵树，例如：

t(left_son,V,right_son)

但如何解决循环？

我可以列出边：

graph([a,b,c,d],[e(a,b),e(b,c),e(c,a),e(c,d)])

要不就