На Wiki есть некий псевдокод:
BFS(start_node, goal_node) {
return BFS'({start_node}, ∅, goal_node);
}
BFS'(fringe, visited, goal_node) {
if(fringe == ∅) {
// Целевой узел не найден
return false;
}
if (goal_node ∈ fringe) {
return true;
}
return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node);
}
Но в нем есть много непонятного, а именно последняя строчка возврата функции.
Суть задания написать программу обхода графа в ширину что бы найти все кратчайшие пути. Суть вопроса - написать псевдокод, который может пройти граф с критериями выше.
Сейчас у меня есть рабочий код, который возвращает один кратчайший ответ и тот написан мягко говоря очень плохо.
Как это работает?
- Получаем новую вершину.;
- Загоняем ее в функцию, помечаем черным цветом;
- Проверяем смежные вершины и если они белые - кидаем в очередь;
- Для каждого элемента запоминаем его родителя в отдельный массив родителей;
- Далее крутим по кругу пока очередь не будет пустая;
- После завершения функции запускаем функцию восстановления пути, которая восстанавливает путь реверсивно, начиная с конечной вершины и заканчивая начальной, с помощью массива с родителями.
Осталось только придумать как заставить программу находить все кратчайшие пути и сделать нормальный поиск ответа по пройденным точкам, если это реально сделать(ибо код реверсиного поиска выглядит отвратительно).