Возврат только вершин в самом кратчайшем пути

Question

Я знаю, что название немного грязное, но я не знаю, как объяснить это лучше.

Что я пытаюсь сделать:

Используя график, найденный в текстовом файле, найдите и распечатайте кратчайший путь (минимальное количество вершин) от вершины A к вершине B.

Примечание: используйте поиск в ширину, а не Дейкстры.

То, что у меня есть:

Рабочий алгоритм, который применяет BFS к графику, но нет хорошего способа распечатать кратчайший путь.

Яс трудом отличая вершину в кратчайшем пути от вершины, которая просто проходит по алгоритму, но не в кратчайшем пути.

Например: Найти кратчайший путь между 0 и4. 0 подключается к 1,2 и 3. 1 подключается к 4. Мой путь оказывается [0,1,2,3,4] вместо [0,1,4].

IЯ не смог найти ни одной темы, задающей тот же вопрос, или какой-либо дополнительной информации о BFS, которая включает это, поэтому я не уверен, что я это способ сложнее, чем есть?

Редактировать: код для тех, кто может быть заинтересован (совсем не уверен, что я избегаю кругов?)

Редактировать 2: Изменен способ сохранения моего пути в стеке.

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];

    q.add(v);
    Stack<Integer> path = new Stack<Integer>();
    while(q.peek() != null) {
        runBFS(q.poll(),w,visited,q,path);
    }
    return path.toString();
} 

private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
    if(visited[v]) {
    }
    else if(v == w) {
        path.add(v);
        q.clear();
    }
    else {
        path.add(v);
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
                q.add(vi.next());
        }
    }
}

Некоторые пояснения к переменным и методам:

v = вершина происхождения

w = целевая вершина

g = граф

vi = обычный итератор, который перебирает соседей v

Спасибо за чтение!

Answer 1

У вас должно быть определенное поле пути для каждой вершины. Таким образом, вы можете отслеживать выбранные вами пути, отсюда и короткий путь. Я буду использовать массив String, как вы использовали логический массив для хранения посещенных вершин.

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];
    String[] pathTo = new String[g.numVertices()];

    q.add(v);
    pathTo[v] = v+" ";
    while(q.peek() != null) {
        if(runBFS(q.poll(),w,visited,q,pathTo))
        break;
    }
    return pathTo[w];
}

private boolean runBFS(int v, int w, boolean[] visited, Queue<Integer> q, String[] pathTo) {
    if(visited[v]) {
    }
    else if(v == w)
        return true; 
    }
    else {
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
            int nextVertex = vi.next();
            pathTo[nextVertex] = pathTo[v] + nextVertex + " ";
            q.add(nextVertex);
        }
    }
    return false;
}

Answer 2

Другое компактное (пространственное) решение, которое предложили нам помощники и которое не использует O (n ^ 2) места для хранения, состоит в том, чтобы каждый узел сохранял только тот узел, с которого он пришел.Это можно сделать, изменив список посещений на целочисленный массив (int[] visited).

шаг 1: инициализируйте список посещений, чтобы каждый элемент был '-1' или «не посещен»

шаг 2: пометить первый узел как посещенный им самим visited[v] = v;

Сделать BFS (как и вы, со следующими изменениями:)

при переходе от v -> v_next:

if(visited[v_next] == -1)
{
  visited[v_next] = v;
  q.put(v_next);
}
// else skip it, it's already been visited

Таким образом, если w достижимо, посещенный [w] сохранит, с какого узла он пришел, с этого узла вы можете вернуться обратно к v и, наконец, распечатать их в обратном порядке.,(Это делается с использованием стека или метода рекурсивной печати.)

Надеюсь, что это имеет смысл.:)

Answer 3

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

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

Answer 4

Вам нужно поместить ваш текущий узел в стек и выводить весь стек только после достижения пункта назначения.