c# - 收集 DAG 的所有路径

Question

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

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

whereForwardStates是当前状态的下一个状态列表。

我有两个特殊状态

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

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

List<List<string>> paths

例如给出如下图

paths应该包含值 {{"initial","a","final"},{"initial","b","final"}}

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

Answer 1

您的算法可能如下所示：

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

您应该得到一个空队列和一个您想要的字符串列表列表。

Answer 2

感谢您的评论，我也在这里使用了建议 https://stackoverflow.com/a/9535898/1497720 （关键是在 BFS/DFS 期间未使用已访问状态）

这是一个没有访问状态的使用 DFS 的版本

 List<List<string>> paths= new List<List<string>>();
            Stack<Tuple<State, List<string>>> working = new Stack<Tuple<State, List<string>>>();
            working.Push(new Tuple<State,
                List<string>>(initialNode,
                new List<string> { initialNode.stateName }));
            do
            {
                Tuple<State, List<string>> curr = working.Pop();


                if (currNexts.stateName == "final")
                {
                    res.Add(curr.Item2);
                }
                else
                {
                    foreach (State currNext in curr.Item1.ForwardStates)
                    {
                        working.Push(new Tuple<State,
                        List<string>>(rnext, curr.Item2.Union(new[] { rnext.stateName }).ToList()));
                    }
                }
            } while (working.Count != 0);