如果我只是不访问 queue_front 节点的子节点而只是将它们推入队列怎么办？还会是BFS吗？

Question

https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem 在这个问题中，我通过（第一种方法）访问 queue_front 节点并将其子节点推入队列而不访问其子节点而不是（第二种方法）访问其所有子节点然后将它们推入队列来尝试 BFS队列。在第一种方法中，测试用例失败了，但在第二种方法中，它通过了。但在这两种情况下，我都使用 BFS。那为什么会失败呢。代码是 below.In 此代码优先方法已启用，它在上述 hackerrank 问题中使某些测试用例失败。第二种方法通过所有测试用例。请查看 bfs 函数。我正在使用邻接表来实现图形。请帮忙！！谢谢！

#include<bits/stdc++.h>
using namespace std;
vector<long> bfs(vector<vector<int>> &graph, int s,int n){
    queue<pair<int,long> > st;
    vector<bool> vis(n+1,0);
    st.push(make_pair(s,0));
    vector<long> cost(n+1,-1);
    cost[s] = 0;
    vis[s] = 1;
    while(!st.empty()){
        pair<int,long> node = st.front();
        st.pop();
        //I am visiting the queue_front element, enabling first approach
        vis[node.first] = 1;
        cost[node.first] = node.second;
        for(long i = 0;i<graph[node.first].size();i++){
            if(!vis[graph[node.first][i]])
            {
                st.push(make_pair(graph[node.first][i],long(node.second)+long(6)));
                //Below 2 lines are commented to disable the second approach
                //cost[graph[node.first][i]] = node.second + 6;
                //vis[graph[node.first][i]] = 1;
            }
        }
    }
    return cost;
}
int main(){
    int q;
    cin>>q;
    while(q--){
        int n,m;
        cin>>n>>m;
        vector<vector<int>> graph(n+1);
        for(long i = 0;i<m;i++){
            int u,v;
            cin>>u>>v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        int s;
        cin>>s;
        vector<long> cost(n+1,-1);
        cost = bfs(graph,s,n);
        cost.erase(cost.begin());
        cost.erase(cost.begin()+s-1);
        for(long i = 0;i<cost.size();i++){
            cout<<long(cost[i])<<" ";
        }
        cout<<endl;
    }
}

Answer 1

当你将它们从队列中弹出时访问节点将与 dfs 相同它不会确保你最短path.if你将访问节点然后将其推入队列它会给你最短路径考虑案例：

节点1以循环形式连接到节点2和节点2与节点3以及节点3与节点1

我们将使用队列> q； pair 的第一个元素是节点，第二个元素是从开始到节点的距离。

案例一：这是一个循环图，起始节点为 1 我们想找到从 1 到 3.we 的最小距离 push 1 into queue.we 将弹出它并将节点 2 和 3 推入队列而不访问 it.when 我们将弹出 2 然后我们访问 2 并推送 3 所以当我们弹出 3 我们将检查它弹出的节点是否等于 3 并且我们存储最小值 distance.so 在这种情况下我们的最小距离是 2.which 我们已经使用深度遍历找到了。

但答案应该是1，因为1和3直接相关

case 2:we 将在将节点推入队列之前访问该节点

开始节点是 1 然后推入 it.visit 2 和 3 然后将两者推入 stack.when 我们将弹出节点 2 我们检查相邻元素并且 3 和 2 都是 visited.so我们将弹出 3 并检查它是否是目标 node.so 我们将存储 distance.so 在这种情况下 dist[1] 到 dist[3]=0+1 即 1.

如果我只是不访问 queue_front 节点的子节点而只是将它们推入队列怎么办？还会是BFS吗？

What if I just dont visit the children of the queue_front node but just push them into the queue? Will it still be BFS?

c++

queue

breadth-first-search

stdvector