c# - 我如何列出有向图中的每条路径？ (C#)

Question

请指出正确的方向或告诉我要查找什么来解决此问题:

我有一个包含“节点”对象的“树”对象。 (实际上它被称为有向图)。每个节点都包含字段字符串“name”和包含下一个节点的“list”。

如何创建从头节点到脚节点的所有可能节点名称的列表？每个列表都包含一条从头到脚的路径。从头到脚的节点数始终相同，即:6。

这是树的样子:

那个图表应该给我:

list 1: n1,n2,n4,n5,n7,n9,n13.
lsit 2: n1,n2,n4,n6,n8,n9,n13.
list 3: n1,n2,n4,n10,n11,n12,n13

等等。

有人能简单地指出我正确的方向吗？我应该使用什么样的递归算法？我应该使用递归方法还是只使用循环？ (我需要在 dikstra 算法的结果上使用它。)

Answer 1

执行 BFS 或 DFS，并跟踪路径和节点。当节点没有更多子节点时，转储路径。请注意，您有一个图形/森林而不是一棵树，但我概述的算法将同样有效。

开始使用 BFS:

Step 1. [n1]
Step 2. [n2(n1), n3(n1)]
Step 3. [n3(n1), n4(n1,n2)]
Step 4. [n4(n1, n2), n4(n1, n3)]
Step 5. [n4(n1, n3), n5(n1, n2, n4), n6(n1, n2, n4), n10(n1, n2, n4)]
Step 6. [n5(n1, n2, n4), n6(n1, n2, n4), n10(n1, n2, n4), n5(n1, n3, n4), n6(n1, n3, n4), n10(n1, n3, n4)]

...

等等。最后你会有你的路。这将被打印出来。您可以在不需要递归的情况下实现此算法。循环直到数组为空。有道理吗？