Поиск по ширине
До сих пор мы изучили разные способы создания представлений графиков. Что теперь? Один естественный вопрос - какие расстояния между любыми двумя узлами графика? Введите алгоритмы обхода графа . Алгоритмы траверса - это алгоритмы для перемещения или посещения узлов в графе. Одним типом алгоритма обхода является алгоритм поиска ширины. Этот алгоритм начинается с одного узла, сначала посещает всех его соседей, которые находятся на одном крае, а затем переходит к каждому из своих соседей. Визуально это то, что делает алгоритм. Чтобы реализовать этот алгоритм, вам нужно будет ввести структуру графика и узел, с которого вы хотите начать. Во-первых, вы хотите знать расстояния от стартового узла. Это вы хотите сначала начать все свои расстояния на некоторое количество, например
Infinity . Это дает ссылку на случай, когда узел может быть недоступен из вашего стартового узла. Затем вы захотите перейти от стартового узла к своим соседям. Эти соседи находятся на одном крае, и в этот момент вы должны добавить одну единицу расстояния до расстояний, которые вы отслеживаете. Наконец, важной структурой данных, которая поможет реализовать алгоритм поиска по ширине, является очередь. Это массив, в котором вы можете добавлять элементы в один конец и удалять элементы с другого конца. Это также известно как структура данных FIFO или First-In-First-Out .
Напишите функцию bfs() которая принимает граф матрицы смежности (двумерный массив) и корень метки узла в качестве параметров. Метка узла будет просто целочисленным значением узла между 0 и n - 1 , где n - общее количество узлов в графе. Ваша функция выведет пары ключ-значение объекта JavaScript с узлом и его удалением от корня. Если узел не может быть достигнут, он должен иметь расстояние до Infinity .