递归实现深度优先搜索时出现编译错误

Question

我不熟悉在我的方法中使用递归。出于多种原因，我倾向于避开它们。但是，对于一个项目，使用递归方法而不是循环方法似乎更容易，因为我正在尝试对图进行深度优先遍历。

由于我不太精通递归，所以我不明白为什么会出现以下错误。

This method must return a result of type LinkedList.Node

我目前的代码是：

public Node DFSTime(Node node){
    if(node == null){
        System.out.println("No path found");
        return null;
    }
    else if(node.element.equals(destinationAirport)){
        return node;
    }
    else{
        stack.push(node);
        DFSTime(node.nextNode);            
    }
}

代码未完成，我还需要实现一些逻辑，但是我不知道如何消除错误。有没有我遗漏的非常基本的东西？

Answer 1

你应该在 else 结束后的函数末尾有一个默认的 return 语句。

Answer 2

在方法条件块 (if-else) 中，您需要确保从所有条件语句中 returning 适当的类型，以便没有 compile-time 错误。在您的情况下，else 块递归调用 DFSTime(..) 而没有 returning 任何东西。

您可能想要 return 通过递归调用调用的引用，如下所示：

public Node DFSTime(Node node){
        if(node == null){
            System.out.println("No path found");
            return null;
        }
        else if(node.element.equals(destinationAirport)){
            return node;
        }
        else{
            stack.push(node);
            Node node = DFSTime(node.nextNode);
            return node;

        }
    }

Answer 3

编译错误的原因很简单。对于所有可能的情况，编译器清楚地告诉我们没有将结果提供给 return。

更重要的是你现在的做法不正确.

it seems to easier to have a recursive method instead of a looping one since I am trying to do Depth First Traversal for a Graph

有一些重要的事情需要考虑：

字段nextNode非常可疑。如果每个 Node 仅包含指向单个节点的引用，那么实际上您根据定义创建的数据结构不是 Graph，而是 单链表。并且为列表实现 DFS 没有意义。每个节点都应指向 节点集合 ，而不是指向单个节点。
您必须以某种方式区分未访问的节点和已访问的节点。否则你可能会无限递归。为此，您可以在 Node 中定义一个 boolean 字段 isVisited，或者将每个访问过的节点放入 HashSet.
既然您已经选择创建 DFS 的递归实现，您不需要创建堆栈。只有迭代实现才需要它。
不要过度使用全局变量。我想您可能希望能够检查是否可以在不重新实例化图表的情况下到达不同的目的地机场。
使用 getter 和 setter 而不是直接访问字段。这是 Java.
中的首选做法

您的方法可能如下所示（element 不必是 String 类型，它只是总体思路的一个示例）：

public Node DFSTime(Node node, String destinationAirport){
    if(node == null || node.isVisited()) {
        return null;
    }
    if (node.getElement().equals(destinationAirport)) {
        System.out.println("The destination airport was found");
        return node;
    }
    
    node.setVisited(true);
    for (Node neighbour: node.getNeighbours()) {
        Node result = DFSTime(neighbour, destinationAirport);
        if (result != null) return result;
    }
    return null;
}

节点可能如下所示：

public class Node {
    private String element;
    private List<Node> neighbours;
    private boolean isVisited;
    
    public Node(String element, List<Node> neighbours) {
        this.element = element;
        this.neighbours = neighbours;
    }
    
    public void setVisited(boolean visited) {
        isVisited = visited;
    }
    
    public boolean isVisited() {
        return isVisited;
    }
    
    public void addNeighbours(Node neighbour) {
        neighbours.add(neighbour);
    }
    
    public String getElement() {
        return element;
    }
    
    public List<Node> getNeighbours() {
        return neighbours;
    }
}

递归实现深度优先搜索时出现编译错误

Compilation error while implementing the Depth first search Recursively

java

algorithm

graph

depth-first-search