在一般树中查找从根节点到给定节点的所有路径

Question

我想在一棵通用树中找到从根节点到给定节点的所有路径。树是一个多层次树，里面可能有圆圈。例如我有这样的数据

a b
a c
a z
b e
b d
e f
f e
c g
e g
g h

我想获取从a到h的所有路径。上面示例的结果是

的两条路径

a    a
b    c
e    g
g    h
h

我试过 Dijkstras 算法，但它只能让我得到最短路径，而且它似乎有点过分了。谁能建议更简单的方法来找到它们？谢谢

Answer 1

似乎只需要一个递归函数，允许历史中没有重复的节点。像这样：

public class FindPath {

    public static void main(String [] args) {
        Node a = new Node("a");
        Node b = new Node("b");
        Node c = new Node("c");
        Node d = new Node("d");
        Node e = new Node("e");
        Node f = new Node("f");
        Node g = new Node("g");
        Node h = new Node("h");
        Node z = new Node("z");
        a.add(b); a.add(c); a.add(z);
        b.add(e); b.add(d);
        e.add(f); e.add(g);
        f.add(e);
        c.add(g);
        g.add(h);
        ArrayList<ArrayList<Node>> viablePaths = new ArrayList<ArrayList<Node>>();
        findPaths(a, "h", new ArrayList<Node>(), viablePaths);
        for (ArrayList<Node> path: viablePaths) {
            print(path);
        }
    }

    public static void findPaths(Node start, String endName, ArrayList<Node> startingPath, ArrayList<ArrayList<Node>> viablePaths) {
        startingPath.add(start);
        for (Node next: start.children) {
            ArrayList<Node> extendedPath = (ArrayList<Node>) startingPath.clone();
            if (next.equals(endName)) {
                extendedPath.add(next);
                viablePaths.add(extendedPath);
            } else {
                boolean nodeAlreadyUsed = false;
                for (Node existingNode: startingPath) {
                    if (next.equals(existingNode)) nodeAlreadyUsed = true;
                }
                if (!nodeAlreadyUsed) {
                    findPaths(next, endName, extendedPath, viablePaths);
                }
            }
        }
    }

    public static void print(ArrayList<Node> path) {
        StringBuffer sb = new StringBuffer();
        for (Node node: path) sb.append(node + " ");
        System.out.println(sb);
    }
}

class Node {
    public String name;
    public ArrayList<Node> children = new ArrayList<Node>();
    public Node(String name) {this.name = name;}
    public boolean equals (Node other) {return other.name.equals(name);}
    public boolean equals (String other) {return other.equals(name);}
    public void add(Node child) {children.add(child);}
    public String toString() {return name;}
}

这将打印：

a b e g h 
a c g h

在一般树中查找从根节点到给定节点的所有路径

Find all the paths from the root node to the given node in a general tree

java

tree

binary-tree

node.js