深度优先搜索列出指向所有末端节点的路径 [英] Depth first search list paths to all end nodes

问题描述

您好，我有一棵树，我想在其中获取从初始(根)节点到所有叶子的路径。

我找到了几个算法，它们列出了图中任意给定两个节点之间的(所有)路径(例如，这样的问题： Graph Algorithm To Find All Connections Between Two Arbitrary Vertices)

对于二叉树，也存在一个算法 http://techieme.in/print-all-paths-in-a-tree/ 但我在一棵有各种分枝因素的树上工作。

有没有更好的方法来实现我想要做的事情，而不是遍历一次树以获得所有树叶，然后结合初始节点对所有树叶运行上述算法？

我在考虑实现简单的DFS，通过一些额外的堆栈来扩展，这些堆栈包含沿着路径到单个叶的所有节点，然后通过循环遍历这些堆栈列出所有句子。

    ArrayList<GrammarNode> discovered = new ArrayList<GrammarNode>();
    Stack<GrammarNode> S = new Stack<GrammarNode>();


    while (!S.empty()) {
        node = S.pop();
        if (!discovered.contains(node)) {
            discovered.add(node);
            System.out.println(node.getWord.getSpelling().trim());
            for (GrammarArc arc : node.getSuccessors()) {
                S.push(arc.getGrammarNode());
            }
        }
    }

更新： 这样做的问题是，为了生成完整的句子，人们总是要追溯到词根。所以我想问题是：如何记住已经被完全访问的节点(这意味着已经浏览了所有子节点)？

推荐答案

打印从根到每个叶的所有路径将意味着打印整个树，因此我只需使用简单的DFS并为每个节点执行以下操作：

• 将其添加到列表/堆栈
• 如果节点有子节点，则对子节点重复此操作
• 如果节点是叶，则打印列表/堆栈
• 从列表/堆栈中弹出节点

示例：

   A
  / 
 B   E
/  / 
C D F G

第一步如下所示：

• 将A放在列表上->{A}
• 把B放在名单上->{A，B}
• 将C放在列表上->{A，B，C}
• 因为C是叶子，所以打印列表(A、B、C)
• 从列表中删除C->{A，B}
• 将D放在列表上->{A，B，D}
• 因为D是叶子，所以打印列表(A、B、D)
• ...

这篇关于深度优先搜索列出指向所有末端节点的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！