收集的DAG的所有路径 [英] Collecting all paths of DAG
本文介绍了收集的DAG的所有路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有向无环图,其中每个节点重新present由国家
I have a directed acyclic graph where each node is represent by a state
public class State{
List<State> ForwardStates;
string stateName;
}
其中, ForwardStates
是下一个状态从当前状态的列表。
where ForwardStates
is a list of next states from the current state.
我有两个特殊的状态
State initialState (name=initial)
State finalState (name=final)
我希望能够找到的所有路径从初始状态开始到最终状态,然后填充
List<List<string>> paths
例如给出的图形像下面的
For example given the graph like the following
路径
应包含的价值
{{初始,一个,最终},{初始,B,最后的}}
paths
should contain the value
{{"initial","a","final"},{"initial","b","final"}}
我应该如何做到这一点很容易在C#中没有递归(如图形可能是很大的)?
How should I achieve this easily in C# without recursion (as the graph might be big)?
推荐答案
您的算法可能会去这样的:
Your algorithm might go like:
- 创建
元组℃的队列;国名单,其中,字符串&GT;&GT;
- 在排队
{初始化状态,新的名单,其中,串&GT; {InitialState.Name}}
- 当队列中有任何项目,
- 出列第一项
- 对于所有非最终推进国在出队的状态,排队
{ForwardState,DequeuedList.ToList()。添加(ForwardState.Name)}
- 如果最后的状态是向前的状态,加上
DequeuedList.ToList()。添加(FinalState.Name)
到您的输出列表中。
- Create a queue of
Tuple<State, List<String>>
. - Enqueue
{ InitialState, new List<string> { InitialState.Name } }
- While the queue has any items,
- Dequeue the first item
- For all non-final forward states in the dequeued state, enqueue
{ ForwardState, DequeuedList.ToList().Add(ForwardState.Name) }
- If final state is a forward state, add
DequeuedList.ToList().Add(FinalState.Name)
to your output list.
您应该结束了一个空的队列,并为你的愿望字符串列表清单。
You should end up with an empty queue and a list of lists of strings as you desire.
这篇关于收集的DAG的所有路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文