c# - 收集DAG的所有路径

Question

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

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

其中 ForwardStates 是当前状态的下一个状态列表。

我有两个特殊状态

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

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

List<List<string>> paths

例如给定如下图

paths 应该包含值{{"初始","a","最终"},{"初始","b","最终"}}

我应该如何在没有递归的情况下在 C# 中轻松实现这一点(因为图形可能很大)？

Answer 1

你的算法可能是这样的:

• 创建 Tuple<State, List<String>> 的队列.
• 排队 { InitialState, new List<string> { InitialState.Name } }
• 当队列中有任何项目时，
  • 出列第一项
  • 对于出队状态中的所有非最终转发状态，入队{ ForwardState, DequeuedList.ToList().Add(ForwardState.Name) }
  • 如果最终状态是前进状态，添加DequeuedList.ToList().Add(FinalState.Name)到你的输出列表。

您最终应该得到一个空队列和一个字符串列表列表。