Поиск В Глубину Php

Поиск в глубину (DFS) - один из методов обхода графов, который позволяет найти все вершины, связанные с заданной стартовой вершиной. Он основан на принципе "погружения" в глубину и может быть реализован на PHP с помощью рекурсии.

Рассмотрим пример реализации DFS на PHP:

function dfs($graph, $start, $visited) {
    $visited[$start] = true;
    echo $start." ";
    $neighbors = $graph[$start];
    foreach($neighbors as $node) {
        if(!$visited[$node]) {
            dfs($graph, $node, $visited);
        }
    }
}

В данном примере функция dfs принимает на вход граф ($graph), стартовую вершину ($start) и массив посещенных вершин ($visited). После посещения стартовой вершины, функция рекурсивно вызывает себя для всех ее соседей, которые еще не были посещены. Рекурсия продолжается до тех пор, пока не будут посещены все вершины.

Использование данной функции:

$graph = array(
    "A" => array("B", "C"),
    "B" => array("A", "D", "E"),
    "C" => array("A", "F"),
    "D" => array("B"),
    "E" => array("B", "F"),
    "F" => array("C", "E")
);
$visited = array();
dfs($graph, "A", $visited);

В данном примере мы обходим граф, начиная с вершины "A". Результатом работы функции будет вывод в консоль всех вершин графа, связанных с вершиной "A":

A B D E C F