Может кто-нибудь объяснить поиск в ширину?

Question

Может кто-нибудь объяснить поиск в ширину, чтобы решить следующие проблемы

Мне нужно найти все пути от 4 до 7

Answer 1

Вы смотрите на все узлы, смежные с вашим начальным узлом. Затем вы просматриваете все узлы рядом с ними (не возвращаясь к узлам, которые вы уже просматривали). Повторяйте до тех пор, пока не будет найден подходящий узел или больше нет узлов.

Для проблемы, которую вы указываете, вы используете описанный выше процесс для построения набора путей, заканчивая любые, которые достигают желаемого узла назначения, и когда ваш граф исчерпан, набор путей, которые так прерваны, является вашим набор решений.

Answer 2

Поиск в ширину (BFS) означает, что вы обрабатываете все дочерние дочерние элементы ваших начальных узлов, прежде чем перейти на более глубокие уровни. В BFS реализована очередь, в которой хранится список узлов, которые необходимо обработать.

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

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

Поскольку вы имеете дело с графиком, а не с деревом, вам нужно сохранить список обработанных узлов, чтобы не зацикливаться.

Как только вы достигнете узла 7, у вас есть соответствующий путь, и вы можете прекратить делать BFS для этого рекурсивного пути. Это означает, что вы просто не добавляете его детей в очередь. Чтобы избежать циклов и узнать точный путь, который вы посетили, при выполнении рекурсивных вызовов BFS пропустите уже посещенные узлы.

Answer 3

Думайте об этом как о сайтах со ссылками на другие сайты на них. Пусть A будет нашим корневым узлом или нашим стартовым сайтом.

A is the starting page    (Layer 1)
A links to AA, AB, AC     (Layer 2)
AA links to AAA, AAB, AAC (Layer 3)
AB links to ABA, ABB, ABC (Layer 3)
AC links to ACA, ACB, ACC (Layer 3)

Это всего три слоя. Вы ищете один слой за раз. Таким образом, в этом случае вы начинаете со слоя A. Если это не соответствует, вы переходите к следующему слою, AA, AB и AC. Если ни один из этих сайтов не является тем, который вы ищете, вы переходите по ссылкам и переходите на следующий уровень. Другими словами, вы смотрите на один слой за раз.

При глубоком поиске (его дополнении) вы переходите от А к АА к ААА. Другими словами, перед уходом в ШИРОКУ вы должны были ГЛУБИТЬ.

Answer 4

Вы проверяете каждый узел, подключенный к корневому узлу. Затем вы проверяете каждый узел, подключенный к предыдущим узлам. И так до тех пор, пока вы не найдете свой ответ.

Обычно каждая итерация проверяет узлы, которые находятся на одинаковом расстоянии от корневого узла.

Answer 5

НАЧАТЬ

4;

4,2;

4,2,1; 4,2,3; 4,2,5;

4,2,1; (сбой) 4,2,3,6; 4,2,5,6; 4,2,5,11;

4,2,3,6,7; (пропуск) 4,2,3,6,8; 4,2,5,6,7; (пропуск) 4,2,5,6,8; 4,2,5,11,12;

4,2,3,6,8,9; 4,2,3,6,8,10; 4,2,5,6,8,9; 4,2,5,6,8,10; 4,2,5,11,12; (сбой)

4,2,3,6,8,9; (сбой) 4,2,3,6,8,10; (сбой) 4,2,5,6,8,9; (сбой) 4, 2,5,6,8,10; (сбой)

END