c# - 收集具有后向和前向链接的 DAG 的所有路径

Question

我有一个有向无环图，其中每个节点都由一个状态表示

public class State{
   List<State> ForwardStates;
   List<State> backStates;
   string stateName;
}

其中 ForwardStates 是通过当前状态的前向链接的状态列表。backStates 是通过当前状态的反向链接的状态列表。

我有两个特殊状态

State initialState (name=initial)
State finalState (name=final)

我希望找到从初始状态到最终状态的所有路径，并填充

List<List<string>> paths

例如给定如下图

反向链接用棕色虚线箭头表示，前向链接由黑色混凝土箭头表示，可能的路径是{{initial, b, a, final},{initial, c, final},{initial, b, initial,final}}

规则是从初始状态开始，必须经过1个或多个后向链路，才能经过前向链路，一旦切换到前向链路，就一直保持前向链路(即不能使用不再有反向链接)。

这个问题是这个问题的延伸(Collecting all paths of DAG)。

Answer 1

做一个DFS从初始状态使用仅使用后向链接的图表。从在此 DFS 期间发现的每个节点(initialState 除外)执行另一个 DFS，直到找到目标的路径(仅使用前向链接)。

对于您在 DFS 期间在反向链接上发现的每个节点 u，路径是

path(initialState,u) ; path(u,finalState)

其中path(u,v)是这一步相关DFS找到的路径。
请注意，它可能会在某个 u 上多次调用 - 您为从 initialState 到 u 找到的每条路径调用它>，因为它是一个不同的必需路径。

---

如果您只需要路径数量，使用 topological sort 可以更快地解决问题和 DP , 但这里不是这种情况。