Найти путь с BFS в графе

Question

Я хочу найти путь между двумя узлами в графе с bfs. Я написал функцию, которая посещает все узлы в правильном порядке (не уверена, что она работает, но мне кажется, что это правильно), но мне нужно сохранить путь (со списком всех ребер, который делает путь), и я не знаю, t знать, как это сделать: \

Может кто-нибудь мне помочь? Заранее спасибо :)

Answer 1

Вы создаете массив p родителей. Поэтому, если p[u] = v есть край от v до u по пути от источника до u. Если родителем исходной вершины является null.

Итак, когда мы находимся в текущей вершине v, перед тем, как вставить свою соседнюю вершину u в очередь, мы делаем p[w] = v. Когда вы найдете целевую вершину, вы возвращаетесь назад в массив p. Начиная с конечной вершины w, p[w] является родителем w, а p[p[w]] является родительским элементом родителя w и т. Д.

Answer 2

Это может быть один из подходов.

В этом подходе вы сохраняете очередь списков, в которых вы получаете список и получаете первый узел из этого списка.

найти adj() этого узла и для каждого узла, который не был посещен, добавить в очередь path+[node] в очереди, также, если цель достигнута, возвращает path+[node].

step 1 : create a queue of to hold the paths. 
step 2 : add the source as [ source ] in the queue 
step 3 : while the queue is not empty get one path from it 
     (as this works for both bfs and dfs thats why "get" not "dequeue" or "pop") 

step 4: get the last node of that path (list) 
step 5: get the adj of that node and for each not explored create a new path i.e oldpath +[adj node] 

step 6:if the adj node is what u want then return the path else add the path to the queue 

Надеюсь, это было полезно.