Используя поиск в ширину: как мне добраться до конечной вершины? - PullRequest
Новая
       15

Используя поиск в ширину: как мне добраться до конечной вершины?

0 голосов
/ 01 апреля 2019

Я не уверен, почему мой код не возвращает верные вершины пути.Он возвращает [abc] вместо [acf], и я не знаю почему.Есть ли что-то, что я здесь упускаю или делаю неправильно в моем алгоритме?Примечание: getNeighbors (String vertex) возвращает соединительные ребра для вершины в своем параметре.

Это тест: мой код останавливается на «assertEquals (« c », route.next ())», потому что он возвращает «b» вместо «c».текущий код моего кода [abc], ожидаемый [acf] 

public class PathingTest {

    @Test
    public void testPathing(){
        Graph cycle = new Graph("graphs/cycle.json");
        Iterator<String> route = cycle.getRoute("d", "b").iterator();
        assertEquals("d",route.next());
        assertEquals("b",route.next());
        assertFalse(route.hasNext());

        Graph tree = new Graph("graphs/tree.json");
        route = tree.getRoute("a", "f").iterator();
        assertEquals("a",route.next());
        assertEquals("c", route.next());
        assertEquals("f", route.next());
        assertFalse(route.hasNext());

        Graph disconnected = new Graph("graphs/disconnected.json");
        assertEquals(null, disconnected.getRoute("a", "f"));
    }
}

1 Ответ

0 голосов
/ 01 апреля 2019

Переменная queue и переменная visited имеют разные цели, но в вашем случае они обновляются одинаково, что неверно.

Вскоре вы добавляете узел к queue во время обработки его родителя (что означает, что в какой-то момент в будущем этот узел также ожидает обработки). Между тем, вы добавляете узел в visited только после того, как обработали его (добавили его дочерние элементы в очередь).

Ваша петля while должна выглядеть следующим образом (обратите внимание на положение вставки в visited). 

while (!queue.isEmpty()) {
    String current = queue.remove();
    path.add(current);

    visited.add(current);

    if (current == end) {
        return path;
    }

    Iterator<String> neighbors = getNeighbors(start).iterator();
    while (neighbors.hasNext()) {
        String n = neighbors.next();

        if (!visited.contains(n)) {
            queue.add(n);
        }
    }
}
...