1
Общий тренд 0-1 алгоритмов BFS: если встречается край с весом = 0, то узел выдвигается на передний край дека, а если вес края равен 1, то он будет сдвинут на задний план от deque.Если ребра не вставлены в deque в отсортированном порядке весов, делает 0-1 BFS для получения правильного ответа?
Если мы случайно нажимаем края, то можем ли 0-1 BFS вычислить правильный ответ? Что, если края введены в deque, не отсортированы по порядку их весов?
Это общий алгоритм 0-1 BFS. Если я пропущу последние, если и другие части и случайным образом надавить на края, то что произойдет?
Для меня это должно сработать, но тогда почему этот алгоритм сделан таким образом?
void bfs (int start)
{
std::deque<int> Q; // double ended queue
Q.push_back(start);
distance[start] = 0;
while(!Q.empty())
{
int v = Q.front();
Q.pop_front();
for(int i = 0 ; i < edges[v].size(); i++)
{
// if distance of neighbour of v from start node is greater than sum of
// distance of v from start node and edge weight between v and its
// neighbour (distance between v and its neighbour of v) ,then change it
if(distance[edges[v][i].first] > distance[v] + edges[v][i].second)
{
distance[edges[v][i].first] = distance[v] + edges[v][i].second;
// if edge weight between v and its neighbour is 0
// then push it to front of
// double ended queue else push it to back
if(edges[v][i].second == 0)
{
Q.push_front(edges[v][i].first);
}
else
{
Q.push_back(edges[v][i].first);
}
}
}
}
}