在有向循环图中查找所有路径的正则表达式

Question

让 G = (V,E,r) 成为一个根据指定的根节点 r 定义的有向图，由一组顶点 V 和一组边 E 组成。该图可能包含循环。任务: 给定 V 中的两个顶点 x 和 y，找到从 x 到 y 的所有路径。

由于允许循环，因此路径集合显然可以是无限的。因此，我想以正则表达式（Kleene 代数）的形式找到路径集合。以下是一些示例：Examples graphs。乘法表示序列，所以路径 abc 表示先 a，然后 b，然后 c。一组路径 a(b+c+d) 表示先 a，然后是 b、c 或 d 中的任何一个。kleene 星号 a* 表示 a 重复零次或更多次，a+ 表示 a 重复一次或更多次。

现在我正在寻找一种算法构建这些表达式的方法。目前我想到的是：

• 构建新的表达式树T。
• 从末尾节点y开始搜索。
• 找到所有y的前任p。
• 对于每个p：
  • 将p作为子节点添加到T中的y。
  • 从p向根回溯路径。如果在途中发现了y，则存在从y到p的循环。因此，p不仅是y的前任，而且(path)*也是p的前任。因此，将(path)*作为子节点添加到p中。
  • 对于所有非循环前任，使用y：= p作为新的结束节点进行递归调用。

最后:

• 反转树，以结束节点结尾
• 将表达式树转换为表达式（直接）

我不确定这是否有效，但是，即使最坏情况下的复杂度也将高于2^n。有人知道这个或类似问题的算法吗？

- Stefan Lutz

---

请展示你所尝试的内容。Stack Overflow旨在帮助人们解决他们代码中的问题，而不是让其他人替他们完成工作。 - Barmar

@Barmar 我觉得原帖作者已经展示了他们尝试过的内容，通过提出可能的算法，并清楚地解释了问题的细节。 - DPenner1

Answer 1

你的算法的总体思路看起来不错。然而，我猜在回溯步骤中可能会有许多特殊情况需要编码处理。特别是，我没有看到这一步骤如何轻松地处理循环内嵌循环的情况，即(path)*本身包含一个需要Kleene星号的术语。

我有另外一个建议。可以将图形转换为NFA，这将允许使用任何众所周知的算法将NFA转换为正则表达式。

要将图形转换为NFA：

• 将节点x设置为起始状态。
• 将节点y设置为唯一的接受状态。
• 对于每个节点a，标记其所有传入边缘a。

- DPenner1