PHP
Чем отличается BFS от DFS
BFS (Breadth-First Search, поиск в ширину):
BFS использует очередь для отслеживания узлов, которые следует посетить. Это означает, что BFS начинает обход с корневого узла и посещает узлы в порядке их добавления в очередь (сначала ближайшие узлы, затем дальнейшие).
<?php
declare(strict_types=1);
function bfs(array $graph, string $startNode): array
{
$visited = [];
$queue = new SplQueue();
$queue->enqueue($startNode);
while (!$queue->isEmpty()) {
$node = $queue->dequeue();
if (!in_array($node, $visited)) {
$visited[] = $node;
foreach ($graph[$node] as $neighbor) {
$queue->enqueue($neighbor);
}
}
}
return $visited;
}
$graph = [
'A' => ['B', 'C'],
'B' => ['A', 'D', 'E'],
'C' => ['A', 'F'],
'D' => ['B'],
'E' => ['B', 'F'],
'F' => ['C', 'E'],
];
print_r(bfs($graph, 'A'));
2 DFS (Depth-First Search, поиск в глубину):
DFS использует стек для отслеживания узлов, которые следует посетить. Это означает, что DFS начинает обход с корневого узла и посещает узлы в порядке их добавления в стек (сначала дальнейшие узлы, затем ближайшие).
<?php
declare(strict_types=1);
function dfs(array $graph, string $startNode): array
{
$visited = [];
$stack = new SplStack();
$stack->push($startNode);
while (!$stack->isEmpty()) {
$node = $stack->pop();
if (!in_array($node, $visited)) {
$visited[] = $node;
foreach ($graph[$node] as $neighbor) {
$stack->push($neighbor);
}
}
}
return $visited;
}
$graph = [
'A' => ['B', 'C'],
'B' => ['A', 'D', 'E'],
'C' => ['A', 'F'],
'D' => ['B'],
'E' => ['B', 'F'],
'F' => ['C', 'E'],
];
print_r(dfs($graph, 'A'));
Обратите внимание, что в этих примерах используется объект SplQueue для реализации очереди в BFS и объект SplStack для реализации стека в DFS. Эти объекты являются частью стандартной PHP библиотеки (SPL).
Жизненные ситуации где может быть полезно BFS или DFS
BFS (Breadth-First Search, поиск в ширину) и DFS (Depth-First Search, поиск в глубину) используются в различных приложениях, в зависимости от конкретной проблемы, которую они решают. Вот некоторые жизненные сценарии, где они могут быть полезны:
-
Социальные сети: BFS может быть использован для поиска друзей друзей на социальной сети. Например, если вы хотите увидеть всех друзей вашего друга и друзей ваших друзей, BFS будет подходящим алгоритмом, так как он начинает поиск с ближайшего уровня и переходит к следующему уровню только после того, как все узлы на текущем уровне были посещены.
-
Web Crawling: Поисковые системы, такие как Google, используют алгоритмы, похожие на BFS, для индексации веб-страниц. Они начинают с одной страницы, затем переходят на все связанные страницы, затем переходят на страницы, связанные со связанными страницами, и так далее.
-
GPS навигация: BFS также может использоваться для поиска кратчайшего пути от одной точки к другой на карте, представленной в виде графа, где узлы представляют собой местоположения, а ребра представляют собой пути между ними.
-
Маршрутизация в сетях: Протоколы маршрутизации в сетях компьютеров, такие как OSPF, используют алгоритмы, похожие на BFS, чтобы определить наиболее эффективный путь для передачи данных от одной точки к другой.
С другой стороны, DFS может быть полезен в следующих сценариях:
-
Решение пазлов: DFS может использоваться для решения таких пазлов, как лабиринты или головоломки на основе графа. Он ищет решение, углубляясь в каждую ветвь графа до тех пор, пока не найдет решение или не достигнет конца ветви.
-
Планирование пути: DFS также может использоваться для планирования пути в ситуациях, когда цель состоит в том, чтобы посетить каждую точку на графе. Например, если вы хотите посетить каждую комнату в здании, DFS может помочь вам спланировать маршрут, чтобы вы не прошли через одну и ту же комнату дважды.
-
Парсинг кода: DFS используется в компиляторах и интерпретаторах для анализа (или парсинга) кода. Он обходит абстрактное синтаксическое дерево (представление структуры кода) от вершины до листьев, применяя правила грамматики.
Leave a reply