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

Question

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

这是测试：我的代码在 "assertEquals("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

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

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

Using breadth first search: how do I get to the end vertex?

java

breadth-first-search