В этом посте рассматривается обход графов, я рассмотрел основы работы с графами и их реализацию в части 1 - Структуры данных графа в JavaScript - Часть 1: основы работы с графами
Существует два алгоритма, которые можно использовать для обхода графа: поиск в глубину (DFS) и поиск в ширину (BFS). С помощью обхода можно найти определенную вершину, путь между двумя вершинами или проверить, связан ли граф, содержит ли он цикл и т. д.
Поиск в глубину
В алгоритме поиска в глубину мы сначала посещаем начальную вершину, затем следуем по пути, пока не будет посещена последняя вершина пути, а затем мы возвращаемся и следуем по следующему пути. т.е. если начальная вершина - A, мы сначала посещаем A, а затем соседа A, а затем соседа соседа A и так далее. Достигнув последней вершины пути (тупика), мы возвращаемся по пути и следуем по следующему пути.
Здесь, допустим, начальная вершина равна 1, мы сначала посещаем 1, а затем 2, а затем 4 (тупик), теперь возвращаемся к 2, а затем к 5 (тупик), а затем возвращаемся к 1, а затем к последним 3 (тупик) .
Заказ DFS будет -
1 → 2 → 4 → 5 → 3
Реализация DFS
Для реализации поиска в глубину мы используем stack в качестве вспомогательной структуры данных для хранения вершин для будущей обработки и object для хранения посещенных вершин, чтобы избежать повторного посещения.
Здесь мы инициализировали stack с начальной вершиной по первому индексу object , называемой visited, и пустым array с именем result для хранения порядка.
Мы будем повторять stack, пока он не станет пустым, и на каждой итерации мы будем извлекать last vertex из stack и проверять, посещена ли вершина или нет. Если вершина не посещена, мы добавим ее в visited object и в result array. И наконец, мы добавим всех соседей этой вершины в stack для будущей обработки.
Поиск в ширину
В алгоритме поиска в ширину мы сначала посещаем начальную вершину, затем ее соседей, затем их соседей и так далее. т.е. если начальная вершина - A, то мы посещаем всех соседей A, а затем посещаем всех соседей соседей A и так далее.
Здесь, скажем, начальная вершина 1, мы сначала посещаем 1, затем 2 и 3, а затем 4 и 5.
Порядок BFS будет -
1 → 2 → 3 → 4 → 5
Реализация BFS
Для реализации поиска в ширину мы используем queue в качестве вспомогательной структуры данных для хранения вершин для будущей обработки и object для хранения посещенных вершин, чтобы избежать повторного посещения.
Здесь мы инициализировали queue с начальной вершиной по первому индексу object , называемой visited, и пустым array с именем result для сохранения порядка.
Мы будем повторять queue, пока он не станет пустым, и на каждой итерации мы будем извлекать first vertex из queue и проверять, посещена ли вершина или нет. Если вершина не посещена, мы добавим ее в visited object и в result array. И наконец, мы добавим всех соседей этой вершины в queue для будущей обработки.
Ссылка Github для списка смежности с методами обхода DFS и BFS.
Не пропустите - Структуры графических данных в JavaScript - Часть 1: Основы работы с графами
