问题标签 [cyclic-graph]

我正在尝试实现一个正则表达式到 NFA 转换器。我已经编写了大部分代码，但是我正在努力寻找一种方法来构建具有循环的图形，因为我对状态（节点）和边的表示。

我的图形表示如下：

我将正则表达式转换为 NFA 的函数基本上是对正则表达式类型的模式匹配，接受正则表达式类型和“最终状态”（NFA 的所有传出边都将去的地方）并返回“开始状态”该正则表达式的（部分构建的）NFA。NFA 片段是通过返回一个使用其传出边列表构造的状态来构建的，其中每个边的结束状态是通过递归调用构造的。

大多数代码都很简单，但是我在为 Kleene 星和 + 构建 NFA 时遇到了麻烦，这需要图中的循环。鉴于我的代表，我最终得到了类似的结果：

显然这不会编译，因为此时 s 是未定义的。但是我也不能添加“rec”关键字，因为类型检查器将（正确地）拒绝这种递归定义的类型，并且我无法通过使用 Lazy 来解决这个问题，因为强制评估“s”将递归地强制它（再次然后再次...）。基本上我在这里有一个先有鸡还是先有蛋的问题-我需要在“状态”引用完全构造之前将其传递到另一个状态，该状态将返回它，但是当然原始状态必须完全构造才能传递在递归调用中。

有没有办法在不使用引用/可变记录的情况下做到这一点？我真的很想尽可能保持它的功能，但鉴于这种情况，我看不到解决办法......有人有建议吗？

我有一个循环有向图，我想知道是否有任何算法（最好是最佳算法）来列出任意两个节点之间的共同后代？与最低共同祖先（LCA）所做的几乎相反。

我是 Prolog 的新手。我试图找出一个问题，我需要检查边缘之间是否存在路径。我完成了循环的非循环图形代码，我的代码将进入无限循环。

我需要通过定义一个新的谓词来处理这种情况： new_path(Start,End,path) 应该消除无限循环。请让我知道如何进行。

我在 Prolog 中写过：

它也处理循环图，当我尝试从同一个节点遍历同一个节点时，我得到一个不规则的输出。

例如：path(x,x,P). 预期输出应该是：

但是，我得到输出：

我怎样才能摆脱这种不需要的情况。谢谢

我正在处理与嵌套组相关的问题。我需要确定一个组所属的所有组以及它所属的所有组。不仅是直系父母和孩子，而且上下层级中的每个人。

到目前为止，我所做的是从上到下的遍历逻辑，即 DFS 使用堆栈来存储未访问的笔记和哈希集来存储已访问的笔记。这样一来，如果结果图中有任何循环，我们就不会进入无限递归。

这部分有效。我遇到的麻烦是，弄清楚如何在遍历期间为每个组存储父母和孩子。请记住，一个组可以有其他组或用户作为成员，我们不想存储重复的信息。

输出应该看起来像一个组列表，其中一个组如下

对于顶点数大于 5 的循环图，在每个节点中运行 BFS 并从这些长度中选择最大值将停止工作。

例如：

以循环方式从 1 到 6 对每个顶点进行编号。

现在，使用 BFS：-从节点 1：

1. 取出节点 1，在队列中添加 2 和 6，将长度增加 1
2. 取出节点 2，在队列中添加 3，将长度增加 1
3. 取出节点 6，在队列中添加 5，将长度增加 1
4. 取出节点 3，在队列中添加 4，将长度增加 1
5. 取出节点 5，什么都不做
6. 取出节点 4，什么都不做

长度已经等于 4，大于直径。

如果循环图存储在邻接表模型中，那么我们使用非常慢的 CTE 进行查询。但是如果有办法将循环图的邻接表模型转换为嵌套集模型，那么我猜查询可能会运行得更快一些。我知道对于一棵树可以进行转换，但我没有找到一种方法来处理图形，尤其是循环图。

如果我们不能转换为嵌套集模型，那么除了邻接表和 CTE 之外，在 RDBMS 中存储和查询循环图的最佳方法是什么？

如何从这样的图中删除所有循环？所有边长都是一，所有边要么是垂直的，要么是水平的。该图已连接。

我想计算为了使图形不包含循环而必须删除的最少边数。

如果您包含示例代码（最好是 C++、C 或 Java），那将非常有帮助。

更新：显然我必须找到顶点和边的数量。我遇到的问题给出了一组指令，例如（下、左、上、下、左、左、上、下）。您从坐标平面中的 (0, 0) 开始，沿指定方向移动一个单位。这将创建一个图表。我如何从这组指令中获得顶点和边的数量？

如何将n个节点之间的给定加权循环图转换为具有最小边和的非循环图？加上一个附加信息，在输出图中每个节点不会有超过 D 个输入边。权重为正

我想将循环图转换为非循环图。有没有可以做到这一点的伪代码？我确实尝试过搜索，但他们中的大多数都返回了基于马尔可夫链或研究文章的数学。

我想编写一个程序来做到这一点，任何指示都会很有用。例如考虑下图。

我在麻省理工学院的一次讲座中看到了一个解决方案，但讲座略过了它，参考了之前教过的东西，无法理解。简而言之，它以一种最终图表示DAG但传达相同路径信息的方式在层中复制节点。

[见 46:59]

https://www.youtube.com/watch?v=OQ5jsbhAv_M

编辑：

我想对循环图问题应用动态编程，例如）说最短路径问题Delta(S,D) where S-> Source node and D->Destination node。由于循环图上的DP是无限算法，我们首先需要将循环图转换为无循环图，然后对其应用动态规划技术。