我发现了等待图(wait-for graphs)，我想知道，是否有有效的算法可以检测在有向图中添加一条边是否会导致出现环路? 所讨论的图是可变的(可以添加或删除节点和边)。我们只需要知道是否存在环路即可(以防止添加一个冒犯边)。 当然，可以使用计算强连通分量(例如Tarjan算法)的算法来...

如何检测有向图是否包含环？我考虑使用宽度优先搜索，但不确定。您有什么想法吗？

假设G是一个包含环的无权有向图。我正在寻找一种算法，它可以找到/创建所有无环图G'，由G中的所有顶点和G的子集组成，使G'足够小以使其成为无环图。 更正式地说：所需算法使用G并创建一组无环图S，其中每个图G'都满足以下属性： G'包含G的所有顶点。 G'包含G的边缘子集，使得G'是无环图...

我正在为一门课程编写一个《卡坦岛》的克隆版。 其中一个额外的加分特性是自动确定哪个玩家拥有最长的道路。 我考虑了一下，似乎对深度优先搜索进行一些轻微变化就可以解决，但我在处理循环检测，如何处理玩家两个初始道路网络的连接以及其他一些细节方面遇到了麻烦。从算法上如何解决这个问题呢？ 对于那些不熟...

我搜索了相关主题并找到了一些信息，但回答要么令人困惑，要么不适用。 我有以下代码：class Thing (val name:String, val refs:IndexedSeq[Ref]) class Ref (val name:String, val thing:Thing) 现在，我...

我已经解决了这里发布的大部分问题，除了最长路径问题。我读过有关最长路径的维基百科文章，如果图是无环的话，这似乎是一个简单的问题，但我的图不是无环的。 那么我该如何解决这个问题呢？采用蛮力法，检查所有可能的路径吗？我该如何开始做呢？ 我知道对于一个具有约18000个节点的图形来说，这将需要很...

我想将一个循环图转换成无环图。有没有伪代码可以实现这个呢？我试过搜索，但大多数结果都基于马尔可夫链或研究文章。 我想编写一个程序来完成这个任务，任何指导都将是有用的。例如考虑下面的图形。 A->B B->C C->A 我在一场MIT讲座中看到了一个解决方案，但是该讲座...

我有一个包含N个节点和2N-3条边的连接非定向图。您可以将该图视为建立在现有初始图上，该初始图具有3个节点和3条边。每个添加到图中的节点都与图中现有节点有2个连接。当所有节点都添加到图中（总共添加N-3个节点）时，构建出最终图。 最初我的问题是，这个图中最多可以访问多少个节点一次（除了初始节...

我有一个类似循环图的结构，由节点对象表示。每个节点要么是标量值（叶节点），要么是n≥1个节点的列表（内部节点）。 由于可能存在循环引用，我不能简单地使用递归的HashCode()函数，它会导致无限递归。 虽然HashCode()部分似乎可以通过标记和忽略已访问过的节点来完成，但我在思考Eq...

假设我有这个简单的类： public class Pair { public readonly object first; public readonly object second; public Pair(object first, object second)...