Разбор BFS-минимальное растояние
Изучаю разные алгоритмы и наткнулся на реализацию "Breadth First Search: Shortest Reach", но не могу понять его работы, в особенности почему повсеместно вычитается 1. Буду благодарен за обьяснение.
n - количество узлов графа, m - количество связей между вузлами в графе, edges - масив начал и концов граней, s - узел с которого начинаем. еденица растояния - 6.
vector<int> bfs(int n, int m, vector<vector<int>> edges, int s) {
vector<int> result(n, -1);
bool *visited = new bool[n];
for(int i = 0; i < n; i++)
visited[i] = false;
list<int> queue;
visited[s-1] = true;
result[s-1] = 0;
queue.push_back(s-1);
while(!queue.empty())
{
s = queue.front();
queue.pop_front();
for(auto edge = edges.begin(); edge !=edges.end(); edge++)
{
int u = (*edge)[0]-1, v = (*edge)[1]-1;
if(u == s && v!=s && !visited[v])
{
visited[v] = true;
result[v]= result[u]+6;
queue.push_back(v);
}
else if(u!=s && v==s && !visited[u])
{
visited[u] = true;
result[u] = result[v] + 6;
queue.push_back(u);
}
}
}
remove_if(result.begin(), result.end(), [](int a){return a==0; });
result.resize(n-1);
return result;
}
Ответы (1 шт):
Так как граф представлен в натуральной нумерации вершины 1...N, а граф работает с вершинами 0...N-1, то везде вычитается -1, чтобы перейти в нужную нумерацию, почему же BFS дает всегда правильный ответ для невзвешенных графов. BFS или поиск в ширину работает таким образом, что для каждой вершины мы сначала перебираем ее соседей, и для них по индукции результат будет dist[cur] = dist[prev]+1. По этой формуле находятся расстояния до всех верши, а массив visited гарантирует что мы не зайдем в одну и ту же вершину более одного раза. Проще визуализировать это для дерева, если мы запустим BFS от корня, то для каждой вершины мы будем перебирать его потомков, и это гарантирует нам правильное расстояние от корня до любой вершины