java - java中的深度优先搜索——如何回到父节点？

Question

我正在尝试递归地在 Java 中进行深度优先搜索。目前，代码在我的图表中运行良好，但当它们不再是可访问的节点时，它永远不会回溯以找到路线。老实说，我有点心理障碍。返回父节点的最佳方式是什么？

到目前为止，这是我的代码:

private final Map<Character, Node> mNodes;
private final List<Edge> mEdges;

public DepthFirstSearch(Graph graph){
    mNodes = graph.getNodes();
    mEdges = new ArrayList<>(graph.getEdges());
    for(Node node : mNodes.values()){
        node.setVisited(false);
    }
}

public void depthFirstSearch(Node source){
    source.setVisited(true);
    List<Node> neighbours = source.getNeighbours(mEdges);
    for(Node node : neighbours){
            if(!node.isVisited()){
                System.out.println(node.getName());
                depthFirstSearch(node);
            }
        }
    }

和 getNeighbour 代码:

public List<Node> getNeighbours(List<Edge> edges) {
        List<Node> neighbours = new ArrayList<>();
        for(Edge edge : edges){
            if(edge.getFrom().equals(this)){
                neighbours.add(edge.getTo());
            }
        }
        return neighbours;
    }

添加了尝试 Jager 想法的代码:

public void depthFirstSearch(Node source){
        source.setVisited(true);
        List<Edge> neighbours = source.getNeighbouringEdges(mEdges);
        for(Edge edge : neighbours){
                if(!edge.getTo().isVisited()){
                    System.out.println(edge.getTo().getName());
                    depthFirstSearch(edge.getTo());
                }else{
                    depthFirstSearch(edge.getFrom());
                }
            }
        }

Answer 1

好吧，通常你有一个根节点，它有子节点。每个 child 都可以有自己的 child 。所以你宁愿这样做:

public void depthFirstSearch(Node source)
{
    for(Node node : source.getChildren())
    {
        System.out.println(node.getName());
        depthFirstSearch(node);
        // and right here you get your back tracking implicitly:
        System.out.println("back at " + node.getName());
    }
}

请注意，我没有必要让成员访问过...

编辑:

既然您提供了数据结构，让我提出另一种方法:

class Node
{
    // all that you have so far...

    private char mId;
    private List<Node> mChildren = new ArrayList<Node>();

    public char getId()
    {
        return mId;
    }
    public List<Node> getChildren()
    {
        return Collections.unmodifiableList(children);
    }

    // appropriate methods to add new children
}

id 替换了 map 的键。然后，您只需从某个地方开始就有一个根 Node mRoot。这是实现树的典型方式。

您可能想直接从子节点向上。然后你还需要一个 private Node parent; 在节点类中(在将子节点添加到私有(private)列表时立即设置为 this 并设置为 null，当被删除)。不过，您不会将其用于回溯，因此上面的深度优先搜索保持不变。