2

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

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个或多个反向链接，才能经过前向链接，一旦切换到前向链接，就一直保持前向链接（即不能再使用后向链接） ）。

这个问题是这个问题的延伸（收集 DAG 的所有路径）。

4

1 回答 1

2

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

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

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

path(u,v)此步骤的相关 DFS 找到的路径 在哪里。
请注意，它可能会被u多次调用 - 您为从initialStateto找到的每个路径调用它u，因为它是不同的必需路径。

如果您只需要路径数量，则可以使用拓扑排序和DP更快地解决它，但这里不是这种情况。

于 2013-02-01T18:36:48.330 回答