无法解决bfs实现中的错误

Question

我已经编写了bfs来查找到每个其他节点的最短路径：

queue<int> q;
dist[s] = 0; // maintains the distance of vertices from s(source).
q.push(s);
while(!q.empty()){
int src = q.front();
q.pop();
vis[src] = 1;          // visited array to keep track of nodes which have been visited

for(int i=0; i<adj[src].size(); i++){ // adj is an adjacency list
if(!vis[adj[src][i]]){
q.push(adj[src][i]);
dist[adj[src][i]] = 6+dist[src];
}
}
}

这为一些未知的测试用例提供了错误的答案和超时。但当我这样做的时候，它通过了所有的测试用例：

queue<int> q;
dist[s] = 0;
vis[s] = 1;
q.push(s);
while(!q.empty()){
int src = q.front();
q.pop();

for(int i=0; i<adj[src].size(); i++){
if(!vis[adj[src][i]]){
q.push(adj[src][i]);
dist[adj[src][i]] = 6+dist[src];
vis[adj[src][i]] = 1;
}
}
}

我不明白为什么会发生这种事。

问题链接：https://www.hackerrank.com/challenges/bfsshortreach/problem

Answer 1

我假设当您将数组命名为vis时，它代表is_node_visited，并且如果并且仅当节点n被访问时，您希望is_node_visited[n]为true。

这就是问题所在。BFS的正确概念是is_node_enqueued。我们希望is_node_enqueued[n]为真，当且仅当节点n曾经入队。第二个代码正是这样做的(除了数组仍然被混淆地称为vis(。

您需要is_node_enqueued而不是is_node_visited的原因是您可能会将同一节点排队两次。下面是一个简单的例子来说明这种情况是如何发生的：

N1 -> N2
N1 -> N3
N2 -> N4
N3 -> N4

我们以N1开始"BFS"。

• 当访问N1时，它将N2和N3排队
• 当访问N2时，它将N4排队
• 当N3被访问时，N4还没有被访问

这是一个有趣的时间-如果您使用前者(即错误的概念(仅在访问N4时停止排队。N4将再次排队。如果使用下面的正确概念，那么算法会注意到N4已经入队，并且不会再次入队。

BFS的线性性能建立在一个节点只处理一次的前提之上。如果我们使用不正确的版本，我们就会打破这种假设，因此您不再在线性时间中处理图形。这就是为什么你会有时间。

一般来说，用于诊断此类问题。一种富有成效的方法是生成一些随机输入。运行两个程序，直到它们产生不同的结果，然后调试问题的原因。