使用广度优先搜索：如何到达终点顶点？

Question

我不确定为什么我的代码没有返回正确的路径顶点。它返回[a b c]而不是[a c f]，我不知道为什么。我在这里是否遗漏了什么或在我的算法中做错了什么？注： getNeighbors（字符串顶点）在其参数中返回顶点的连接边。

这是测试：我的代码停止在“断言等式（”c“，route.next（））”，因为它返回“b”而不是“c”。我的代码的当前输出是 [a b c]，预期的是 [a c f]

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"));

    }

}

Answer 1

变量和变量具有不同的用途，但在您的情况下，它们以相同的方式进行更新，这是不正确的。queuevisited很快，您将在处理其父节点时将节点添加到 （这意味着在将来的某个时间点，该节点也希望得到处理）。同时，只有在处理完节点（将其子节点添加到队列）后，才将其添加到 该节点。queuevisited您的循环应如下所示（请注意插入的位置）。whilevisitedwhile (!queue.isEmpty()) {&nbsp; &nbsp; String current = queue.remove();&nbsp; &nbsp; path.add(current);&nbsp; &nbsp; visited.add(current);&nbsp; &nbsp; if (current == end) {&nbsp; &nbsp; &nbsp; &nbsp; return path;&nbsp; &nbsp; }&nbsp; &nbsp; Iterator<String> neighbors = getNeighbors(start).iterator();&nbsp; &nbsp; while (neighbors.hasNext()) {&nbsp; &nbsp; &nbsp; &nbsp; String n = neighbors.next();&nbsp; &nbsp; &nbsp; &nbsp; if (!visited.contains(n)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; queue.add(n);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}