Как найти расстояние между двумя узлами, используя BFS?

Я написал этот код BFS на c ++, используя псевдокод википедии.
Функция принимает два параметра s, t. Где s — это исходный узел, а t — это цель, если целью является fount, поиск возвращает саму цель или же возвращает -1.
Вот мой код:

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

struct vertex{
vector<int> edges;
bool visited;
};

int dist = 0;

int BFS(vertex Graph[],int v,int target){
deque<int> Q;
Q.push_front(v);
Graph[v].visited = true;
while(!Q.empty()){
int t = Q.back();
Q.pop_back();
if(t == target){
return t;
}
for(unsigned int i = 0;i < Graph[t].edges.size();i++){
int u = Graph[t].edges[i];
if(!Graph[u].visited){
Graph[u].visited = true;
Q.push_front(u);
}
}
}
return -1;
}

int main(){
int n;
cin >> n;
vertex Graph[n];
int k;
cin >> k;
for(int i = 0;i < k; i++){
int a,b;
cin >> a >> b;
a--;
b--;
Graph[a].edges.push_back(b);
Graph[b].edges.push_back(a);
}

for(int i = 0;i < n; i++){
Graph[i].visited = false;
}

int s,t;
cin >> s >> t;

cout << BFS(Graph,s,t);

}

Я прочитал это в Википедии:

Поиск в ширину может использоваться для решения многих задач теории графов, например:
Нахождение кратчайшего пути между двумя узлами u и v (длина пути измеряется числом ребер>>)

Как изменить функцию BFS, чтобы она возвращала кратчайший путь от s до t и возвращала -1, если пути не существует?

4

Решение

Когда вы генерируете новый узел, следите за идентификатором родителя, который сгенерировал этот узел. Затем, когда вы достигнете цели, вы просто отследите родителей назад, пока не достигнете начального состояния. Например, вы можете пометить начало как своего родителя, что означает, что это начальное состояние. Или просто используйте предопределенное значение (-1), чтобы сказать, что нет родителя.

Таким образом, в вашем коде вместо пометки состояния как посещенного есть родительский идентификатор. Родительские идентификаторы могут быть изначально установлены в -1, а затем обновлены при их изменении. Идентификатор родителя может просто указывать местоположение в структуре графа родителя.

3

Другие решения

Поиск в ширину по определению посещает все узлы на расстоянии d от начальной точки до посещения любых узлов на расстоянии d+1, Поэтому, когда вы пересекаете график в первом порядке, когда вы впервые сталкиваетесь с целевым узлом, вы попадаете туда по кратчайшему маршруту.

Натан С. ответ верный, хотя я надеюсь, что этот ответ дает некоторую интуицию о том, почему это работает. Комментарий Пола Диня также верен; Вы можете довольно просто изменить ответ Натана, чтобы отслеживать расстояние, а не фактический путь.

5

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector