收集的DAG的所有路径与前后链接 [英] Collecting all paths of DAG with backward and forward links

问题描述

我有向无环图，其中每个节点重新present由国家

I have a directed acyclic graph where each node is represent by a state

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

其中， ForwardStates 是国家通过从当前状态正向链接列表。 和 backStates 是国家通过从当前状态反向链接列表。

where ForwardStates is a list of states via forward links from the current state. and backStates is a list of states via backward links from the current state.

我有两个特殊的状态

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

我希望能够找到的所有路径从初始状态开始到最终状态，并在

I wish to find all paths the start from initial state to final state, and populated in

List<List<string>> paths

例如给出的图形像下面的

For example given the graph like the following

如果反向链接是由褐色的虚线箭头和psented重新$ P $ 前向链路重新被黑的具体箭头psented $ P $， 可能的路径是 {{初期，B，A，最终}，{初期，C，最终}，{初期，B，声母，韵母}}

Where backward links are represented by brown dotted arrow and forward links is represented by black concrete arrow, the possible paths are {{initial, b, a, final},{initial, c, final},{initial, b, initial,final}}

该规则是，从最初的状态，它必须通过1个或更多的反向链接，在经过前向链路，一旦切换到转发链接，它会不断转发链接（即，它不能使用反向链接了）。

The rule is that from initial state, it must go through 1 or more backward links, before go through forward link, and once it switch to forward link, it will keep to forward links （i.e., it can't use the backward links anymore).

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

This question is an extension of this question(Collecting all paths of DAG).

推荐答案

做一个 DFS 从初始状态使用它仅使用的反向链接的图表。从各做一套DFS直到找到路径目标这一DFS（除了初始化状态）时发现的节点（使用只向前链接）。

Do a DFS from initial state using the graph which using only backward links. From each of the nodes discovered by during this DFS (except initialState) do another DFS until you find the path to the target (using forward links only).

有关 U 你DFS期间反向链接发现的每一个节点，路径为

For each node u you discovered during DFS on backward links, the path is

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

其中，路径（U，V）是由相关的DFS发现这一步的路径。
请注意，这可能在一定调用 U 超过一次 - 你调用它为你的的初始化状态到 U ，因为它是一个不同的必要路径。

Where path(u,v) is the path found by the relevant DFS for this step.
Note that it might be invoked on a certain u more then once - you invoke it for each path you find from initialState to u, since it is a different required path.

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

If you only need number of paths it could be solved faster using topological sort and DP, but it is not the case in here.

这篇关于收集的DAG的所有路径与前后链接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！