Что, если я просто не буду посещать дочерние элементы узла queue_front, а просто поставлю их sh в очередь? Будет ли еще BFS?

Question

https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem В этой задаче я попробовал BFS, просто (первый подход) посетив узел queue_front и поместив его дочерние узлы в очередь, не посещая его дочерние узлы вместо (второй подход) посещения всех своих потомков, а затем помещает их в очередь. В первом подходе тестовые примеры не прошли, но во втором подходе все прошло. Но в обоих случаях я использую BFS. Так почему же тогда он не работает? Код ниже. В этом коде включен первый подход, который не дает результатов в некоторых тестовых примерах в указанной выше проблеме хакерского ранга. Второй подход проходит все тесты. Посмотрите, пожалуйста, на функцию 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, это не гарантирует вам кратчайший путь. Если вы посетите узлы, то pu sh это в очереди, это даст вам кратчайший путь, учитывая случай :

узел 1 связан с узлом 2, а узел 2 с узлом 3 и узел3 с узлом node1 в форме cycli c

мы будем использовать очередь > q; первый элемент пары - это узел, а второй элемент - это расстояние до узла от начала.

Случай 1: это циклический c граф с начальным узлом как 1, мы хотим найти минимальное расстояние от 1 до 3 .we pu sh 1 в очередь. мы вытолкнем его, а pu sh node 2 и 3 в очередь, не посещая его. когда мы выскочим 2, мы посетим 2 и pu sh 3, поэтому, когда мы pop out 3 мы проверим, что всплывающий узел равен 3, и мы сохраняем минимальное расстояние. поэтому в этом случае наше минимальное расстояние равно 2, что мы выяснили с помощью обхода глубины.

Но ответ должен быть 1, поскольку 1 напрямую связан с 3.

случай 2: мы посетим узел, прежде чем помещать его в очередь

начальный узел равен 1 и pu sh it.visit 2 и 3 а затем pu sh оба в стек. когда мы вытолкнем узел 2, мы проверяем соседние элементы, и оба 3 и 2 посещены. поэтому мы вытолкнем 3 и проверим, является ли он узлом назначения. поэтому мы сохраним расстояние. поэтому в этом случае от dist [1] до dist [3] = 0 + 1, что равно 1.