java - 使函数中的逻辑递归

Question

背景:想象一下我有一个小机器人。我将这个机器人放在 map (图表)中的某个节点上。机器人可以调用 giveMeMapCopy() 方法来获取他所在的整个 map 的副本。我想给我的小机器人一个函数，通过它他可以使用广度优先遍历找到到导出节点的最短路径.这是此类 map 的示例:

我在 YouTube 上看过关于如何对图进行广度优先遍历的视频，所以我很清楚需要做什么。问题是，我发现很难使我的逻辑递归。这是我的代码:

public class Robot
{
    // fields required for traversal
    private Queue<ArrayList<String>> queue;
    private ArrayList<ArrayList<String>> result;
    private String workingNode;
    private ArrayList<String> routeSoFar;

    private Queue<String> knownShortestPath;

    public Robot() {
        queue = new LinkedList<ArrayList<String>>();
        result = new ArrayList<ArrayList<String>>();
        routeSoFar = new ArrayList<String>();
        knownShortestPath = new LinkedList<String>();
    }

    // Runs when Robot has reached a node.
    public void enterNodeActions() {
        knownShortestPath = determineIdealPath();
    }

    // Runs to determine where to go next
    public String chooseNextNode() {
        if(!knownShortestPath.isEmpty())
        {
            // TODO: Need to go through the 
        }
    }

    public LinkedList<String> determineIdealPath()
    {
        try {
            // Get the map
            Map m = giveMeMapCopy();

            // Get all entry nodes of map
            Set<String> entryNodes = m.getEntryNodes();

            /*
             * Loop through all Entry nodes, and find out where we are.
             * Set that as current working node.
             */
            for (String n : entryNodes) {
                if(n == getMyLocation())
                {
                    workingNode = n;
                }
            }

            // All enighbours of working node.
            Set<String> neighboursNames = getNeighboursNames(workingNode);

            /*
             * For each neighbour, construct a path from working node to the neighbour node
             * And add path to Queue and Result (if not already present).
             */
            for(String node : neighboursNames)
            {
                if(!node.equals(getMyLocation()))
                {
                    ArrayList<String> route = new ArrayList<String>();
                    route.add(getMyLocation());
                    route.add(node);
                    if(!containsRoute(result, route))
                    {
                        if(!containsRoute(queue, route))
                        {
                            queue.add(route);                           
                        }
                        result.add(route);
                    }
                }
            }       
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

我希望递归发生的地方是在我遍历了 Entry 节点 [ A ] 的所有邻居之后，我想移动到下一个 [ B ] 并为此做同样的事情，即遍历它的每个邻居(忽略 A，因为它已经存在于结果列表中)并将它们添加到队列和结果列表中。

我希望问题很清楚，如果没有请告诉我，我会尽力澄清任何不清楚的地方。

Answer 1

广度优先搜索通常没有递归，因为它基于队列(在您的情况下是部分路径)。另一方面，深度优先搜索基于堆栈，可以很自然地使用递归函数的调用堆栈来实现。