Сделать логику в функции рекурсивной

Question

Фон: представьте, у меня есть маленький робот. Я помещаю этого робота в какой-то узел на карте (график). Робот может вызвать метод giveMeMapCopy(), чтобы получить копию всей карты, в которой он находится. Я хочу дать моему маленькому роботу функцию, с помощью которой он может использовать обход в ширину, чтобы найти кратчайший путь к узлу выхода., Вот пример такой карты:

Я смотрел видео на 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

Поиск в ширину обычно выполняется без рекурсии, так как он основан на очереди (частичный путь в вашем случае). Поиск в глубину, с другой стороны, основан на стеке, который может быть реализован вполне естественно с помощью стека вызовов рекурсивной функции.

Answer 2

По сути, вам нужно реализовать алгоритм Дейкстры или нечто подобное, чтобы найти кратчайший путь между источником и пунктом назначения в графе.

Вы можете найти такую ​​реализацию в Java здесь. Просто установите все веса в 1,