代码之家 › 专栏 › 技术社区 › see_sharp_guy

如何列出有向图中的每条路径?C

tree recursion list c#

see_sharp_guy · 技术社区 · 17 年前

请为我指出正确的方向,或者告诉我应该查找什么来解决这个问题:

如何创建从头节点到脚节点的所有可能节点名称的列表?

这就是树的样子:

alt text

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

4 回复 | 直到 9 年前

Ryan Oberoi 17 年前

执行BFS或DFS,并跟踪节点的路径。当节点没有更多子节点时,转储路径。请注意,你有一个图/林而不是树,但我概述的算法也会起作用。

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)]

...