使用广度优先搜索:如何到达结束顶点?
Using breadth first search: how do I get to the end vertex?
我不确定为什么我的代码没有返回正确的路径顶点。它返回 [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"));
}
}
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);
}
}
}
我不确定为什么我的代码没有返回正确的路径顶点。它返回 [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"));
}
}
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);
}
}
}