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

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

您的循环应如下所示（请注意插入的位置）。whilevisited

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

        }

    }

}