regex - 查找有向循环图中的所有路径作为正则表达式

Question

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

由于循环是允许的，路径集显然可以是无限的。因此，我想以正则表达式(Kleene Algebra)的形式找到路径集。这里有几个例子:Examples graphs .乘法表示序列，所以路径 abc 表示首先是 a，然后是 b，然后是 c。一组路径 a(b+c+d) 表示首先是 a，然后是 b、c 或 d。 kleene 星号 a* 表示 a 重复零次或多次，a+ 表示 a 重复一次或多次。

现在我正在寻找一种通过算法构建这些表达式的方法。到目前为止我想出了什么:

• 构建新的表达式树T。
• 从结束节点 y 开始搜索。
• 找到 p 到 y 的所有前辈。
• 对于每个p:
  • 将p作为子节点添加到T中的y。
  • 回溯树上从 p 到根的路径。如果沿途找到y，则存在从y到p的循环。因此，不仅 p 是 y 的先行者，而且(path)* 也是 p 的前身。因此，将(path)*作为子节点添加到p。
  • 对于所有非循环前导，以y := p作为新的结束节点递归调用。

最后:

• 反转树，使其以结束节点结束
• 将表达式树转换为表达式(直接)

不确定这是否可行，但是，我猜最坏情况下的复杂度也会高于 2^n。有谁知道这个或类似问题的算法？

Answer 1

您的算法的总体思路似乎很合理。但是，我猜测在回溯步骤中可能有许多您必须编写代码的特殊情况。特别是，我没有看到该步骤的简单方法来解释循环中的循环，即 (path)* 本身包含一个需要 Kleene 星号的术语。

不过我有单独的建议。该图可以转换为 NFA，这将允许使用 well known algorithms 中的任何一个。将 NFA 转换为正则表达式。

将图形转换为 NFA:

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