Как найти путь в ориентированном графе?

Question

[ne_tot_net]

В чём ошибка? Алгоритм посещает только ближайших соседей.

public boolean path(int from, int to) {
        //массив посещений графов
        boolean[] visited = new boolean[getAllNodes().size()];
        dfs(from, visited);

        return visited[to];
    }

    public void dfs(int index, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();

        stack.push(index);
        visited[index] = true;

        while(!stack.isEmpty()) {
            Integer nodeIndex = stack.pop();
            visited[nodeIndex] = true;
            //Заполняем список потомков
            List<Integer> neighboursList = new ArrayList<>(getChildrenOf(index));

            for(Integer neighbour: neighboursList) {
                if(!visited[neighbour]) {
                    stack.push(neighbour);
                }
            }
        }
        for (int i = 0; i < visited.length; i++) {
        }
    }

Граф
И можно ли с помошью данного алгоритма запоминать путь, а не только его наличие true/false

Answer 1

[TwoBlueCats]

0) у вас в коде есть цикл, который ничего не делает, его можно удалить.
1) в строчке, где получается список соседей используется неправильная переменная. Текущая вершина хранится в nodeIndex.
2) запоминать можно. Для этого либо используют дополнительный массив, в который запоминают "предка" вершины v, то есть такую вершину u, после рассмотрения которой, добавили в стек v. В результате для получения пути надо будет размотать цепочку предков от финальной вершины до стартовой
2.5) если требуется кратчайший путь в невзвешенном графе (все ребра одинаковые), то стоит использовать алгоритм BFS (использовать очередь вместо стека). Если граф взвешенный, то использоваться алгоритм Дейсктры

Answer 2

[dmshar]

1. Ответ на ваш вопрос - "Можно".
2. Предвидя ваш следующий вопрос - " а как это можно сделать" - отвечу сразу, Не знаю, какой путь вы там решили искать (вы даже не удосужились нам об этом сообщить - а зачем, все же должны бегом побежать догадываться, какую там задачу вам задали на дом и вы не осилили, - ну да ладно) - но начните поиск путей в ориентированном графе с алгоритма Дейсктры. 99% вопросов отпадут (если осилите, конечно). За остальными непонятками - возвращайтесь сюда, попробуем помочь.