Руководство для начинающих по BFS и DFS в JavaScript
1 марта 2023 г.Поиск в ширину (BFS) и поиск в глубину (DFS) — это два фундаментальных алгоритма, используемых в компьютерных науках и анализе данных для обхода и поиска таких структур данных, как графы и деревья.
Эти алгоритмы можно применять ко многим задачам, таким как поиск кратчайшего пути между двумя точками, проверка циклов в графе или поиск определенных элементов в структуре данных.
В этой статье мы рассмотрим основы алгоритмов BFS и DFS, предоставим примеры их использования с различными структурами данных и объясним, как они работают с помощью кода JavaScript.
К концу этой статьи вы будете хорошо понимать оба алгоритма и сможете применять их в своих проектах.
Обзор
BFS – это алгоритм обхода графа, который посещает все узлы графа или дерева в порядке уровней, то есть посещает все узлы на заданной глубине, прежде чем перейти к следующей глубине. Чтобы реализовать BFS в JavaScript, мы обычно используем структуру данных очереди, чтобы отслеживать узлы, которые нам нужно посетить в следующий раз.
DFS — это еще один алгоритм обхода графа, используемый для посещения всех узлов в графе или дереве. В отличие от BFS, DFS посещает узлы в порядке глубины, то есть исследует как можно дальше каждую ветвь перед возвратом.
В JavaScript мы можем реализовать DFS, используя структуру данных стека, чтобы отслеживать узлы, которые нужно посетить в следующий раз. Это позволяет нам посещать узлы в порядке глубины, сначала исследуя последний посещенный узел и его непосещенные соседи, прежде чем переходить к следующему узлу.
BFS & Обход DFS для графика
Давайте рассмотрим следующий график:
A -- B -- C
| |
D -- E -- F
Чтобы представить этот граф в JavaScript, мы можем использовать список смежности:
const graph = {
A: ['B', 'D'],
B: ['A', 'C', 'E'],
C: ['B'],
D: ['A', 'E'],
E: ['B', 'D', 'F'],
F: ['E'],
};
Реализация BFS с использованием очереди для обхода графа:
function bfs(graph, start) {
const queue = [start];
const visited = new Set();
const result = [];
while (queue.length) {
const vertex = queue.shift();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
for (const neighbor of graph[vertex]) {
queue.push(neighbor);
}
}
}
return result;
}
bfs(graph, 'A'); // ['A', 'B', 'D', 'C', 'E', 'F']
В этом примере алгоритм BFS реализован с использованием структуры данных очереди, которая содержит узлы, подлежащие обработке, в порядке их обнаружения.
Набор посещений используется для отслеживания узлов, которые уже были посещены, а массив результатов хранит порядок, в котором были посещены узлы.
Начнем с добавления начального узла в очередь и его обработки. Затем мы добавляем его соседей в очередь и обрабатываем их в том порядке, в котором они были добавлены. Мы повторяем этот процесс до тех пор, пока не останется узлов для обработки.
Наконец, мы возвращаем массив результатов, содержащий узлы в порядке их посещения алгоритмом BFS.
Реализация DFS с использованием стека для данного графа:
function dfs(graph, start) {
const stack = [start];
const visited = new Set();
const result = [];
while (stack.length) {
const vertex = stack.pop();
if (!visited.has(vertex)) {
visited.add(vertex);
result.push(vertex);
for (const neighbor of graph[vertex]) {
stack.push(neighbor);
}
}
}
return result;
}
dfs(graph, 'A'); // ['A', 'D', 'E', 'F', 'B', 'C']
В этом примере алгоритм DFS реализован с использованием структуры данных стека, которая содержит узлы, подлежащие обработке, в порядке их обнаружения.
Набор посещений используется для отслеживания узлов, которые уже были посещены, а массив результатов хранит порядок, в котором были посещены узлы. Начнем с добавления начального узла в стек и его обработки.
Затем мы добавляем его соседей в стек и обрабатываем их в том порядке, в котором они были добавлены. Мы повторяем этот процесс до тех пор, пока не останется узлов для обработки. Если мы встречаем узел, который уже был посещен, мы просто пропускаем его и переходим к следующему узлу.
Наконец, мы возвращаем результирующий массив, содержащий узлы в порядке их посещения алгоритмом DFS.
BFS & Обход DFS для дерева
Давайте рассмотрим следующее дерево:
1
/
2 3
/ /
4 5 6 7
Пример реализации этого дерева в JS:
function createNode(value, left = null, right = null) {
return { value, left, right };
}
const tree = createNode(1,
createNode(2,
createNode(4),
createNode(5)
),
createNode(3,
createNode(6),
createNode(7)
)
);
Реализация BFS с использованием очереди для обхода графа:
function bfs(node) {
if (!node) {
return [];
}
const queue = [node];
const result = [];
while (queue.length) {
const current = queue.shift();
result.push(current.value);
if (current.left) {
queue.push(current.left);
}
if (current.right) {
queue.push(current.right);
}
}
return result;
}
bfs(tree); // [1, 2, 3, 4, 5, 6, 7]
Это решение BFS реализует обход дерева в ширину с использованием структуры данных очереди. Алгоритм начинается с добавления корневого узла в очередь и его обработки. Затем он удаляет из очереди первый узел и добавляет его значение в массив результатов.
Затем алгоритм проверяет, есть ли у исключенного из очереди узла левый дочерний узел, и ставит его в очередь, если он существует. Затем он проверяет, есть ли у исключенного из очереди узла правильный дочерний узел, и ставит его в очередь, если он существует. Алгоритм повторяет этот процесс до тех пор, пока в очереди не останется узлов.
Если входной узел нулевой, возвращается пустой массив. Массив результатов содержит значения узлов в порядке их посещения алгоритмом BFS.
Реализация DFS с использованием стека для обхода графа:
function dfs(node) {
if (!node) {
return [];
}
const stack = [node];
const result = [];
while (stack.length > 0) {
const current = stack.pop();
result.push(current.value);
if (current.right) {
stack.push(current.right);
}
if (current.left) {
stack.push(current.left);
}
}
return result;
}
dfs(tree); // [1, 2, 4, 5, 3, 6, 7]
Это решение DFS реализует обход дерева в глубину с использованием структуры данных стека. Алгоритм начинается с добавления корневого узла в стек и его обработки. Затем он извлекает последний узел из стека и добавляет его значение в массив результатов.
Затем алгоритм проверяет, есть ли у извлеченного узла правильный дочерний узел, и помещает его в стек, если он существует.
Затем он проверяет, есть ли у извлеченного узла левый дочерний узел, и помещает его в стек, если он существует. Алгоритм повторяет этот процесс до тех пор, пока в стеке не останется узлов. Если входной узел нулевой, возвращается пустой массив.
Массив результатов содержит значения узлов в порядке их посещения алгоритмом DFS.
Заключение
В заключение следует отметить, что и BFS, и DFS являются мощными алгоритмами, которые можно использовать для обхода самых разных структур данных. BFS — отличный выбор для поиска кратчайшего пути между двумя точками или для обхода структуры данных уровень за уровнем.
Это особенно эффективно, когда структура данных имеет много уровней с небольшим количеством узлов. С другой стороны, DFS хорошо подходит для поиска определенного узла или для более глубокого изучения ветви структуры данных.
Обычно это предпочтительнее, когда возникает вопрос об использовании памяти или когда структура данных имеет много узлов с небольшим количеством уровней.
Оригинал