无法解决 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;
        }
    }
}

我不明白为什么会这样。

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

Answer 1

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

这就是问题所在。 BFS 的正确概念是 is_node_enqueued。当且仅当节点 n 曾经入队时，我们希望 is_node_enqueued[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的线性性能建立在一个节点恰好被处理一次的前提之上。如果我们使用不正确的版本，我们就打破了这个假设，因此您不再以线性时间处理图形。这就是你超时的原因。

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

无法解决 bfs 实现中的错误

unable to resolve the error in bfs implementation

c++

graph-algorithm

breadth-first-search