PHP: Алгоритм поиск в ширину
Поиск в наборе данных с помощью алгоритма «Поиск в ширину». Ищет путь с минимальным количеством переходов.
Сначала нужно представить данные в виде невзвешенных графов. Граф моделирует набор связей между элементами из набора.
В качестве примера сделаем поиск пути между станциями метро. В php граф можно представить в виде массива. Ключ - это уникальное название станции метро. Значение - это список станций, куда можно отправиться с текущей станции (ключа). Пересадочные станции - это разные станции. Отличие от обычных только в том, что они расположены близко друг к другу.
$graph = [ ... 'Пушкинская' => [ 'Владимирская', 'Технологический институт 1', 'Звенигородская' ], 'Технологический институт 1' => [ 'Пушкинская', 'Балтийская', 'Технологический институт 2' ], ... 'Технологический институт 2' => [ 'Сенная площадь', 'Фрунзенская', 'Технологический институт 1' ], 'Фрунзенская' => [ 'Технологический институт 2', 'Московские ворота' ], ... ];
Функция проверяет есть ли путь между указанными станциями. Возвращает true или false.
function isPathExists( $from, $to ) { $checked = []; $queue = []; if( !isset( $this->graph[ $from ] ) ) { return false; } $queue[] = $this->graph[ $from ]; while( sizeof( $queue ) > 0 ) { $node = array_pop( $queue ); foreach( $node as $station ) { if( !array_key_exists( $station, $checked ) ) { array_unshift( $queue, $this->graph[ $station ] ); } $checked[ $station ] = true; if( $station == $to ) { return true; } } } return false; } var_dump( isPathExists( 'Зенит', 'Купчино' ) ); // > bool(true) var_dump( isPathExists( 'Купчино', 'Зенит' ) ); // > bool(true) var_dump( isPathExists( 'Купчино', 'Станция метро 3/4' ) ); // > bool(false)
Функция возвращает путь между указанными станциями.
function getPath( $from, $to ) { $checked = []; $queue = []; $queue[] = $this->graph[ $from ]; $path = []; foreach( $this->graph[ $from ] as $nextStation ) { $path[ $nextStation ] = [ $from ]; } while( sizeof( $queue ) > 0 ) { $node = array_pop( $queue ); foreach( $node as $station ) { if( !array_key_exists( $station, $checked ) ) { array_unshift( $queue, $this->graph[ $station ] ); foreach( $path as $prevStation => $subPath ) { if( $prevStation == $station AND $station != $from AND $station != $to ) { foreach( $this->graph[ $station ] as $nextStation ) { $path[ $nextStation ] = array_merge( [ $prevStation ], $subPath ); } unset( $path[ $prevStation ] ); } } } $checked[ $station ] = true; if( $station == $to ) { $path = $path[ $to ]; array_unshift( $path, $to ); return array_reverse( $path ); } } } return []; } var_dump( getPath( 'Зенит', 'Купчино' ) ); // > array(14) { [0]=> string(10) "Зенит" [1]=> string(20) "Приморская" [2]=> string(32) "Василеостровская" [3]=> string(25) "Гостиный двор" [4]=> string(31) "Невский проспект" [5]=> string(27) "Сенная площадь" [6]=> string(49) "Технологический институт 2" [7]=> string(22) "Фрунзенская" [8]=> string(33) "Московские ворота" [9]=> string(22) "Электросила" [10]=> string(21) "Парк Победы" [11]=> string(20) "Московская" [12]=> string(16) "Звёздная" [13]=> string(14) "Купчино" } var_dump( getPath( 'Купчино', 'Зенит' ) ); // > array(14) { [0]=> string(14) "Купчино" [1]=> string(16) "Звёздная" [2]=> string(20) "Московская" [3]=> string(21) "Парк Победы" [4]=> string(22) "Электросила" [5]=> string(33) "Московские ворота" [6]=> string(22) "Фрунзенская" [7]=> string(49) "Технологический институт 2" [8]=> string(27) "Сенная площадь" [9]=> string(31) "Невский проспект" [10]=> string(25) "Гостиный двор" [11]=> string(32) "Василеостровская" [12]=> string(20) "Приморская" [13]=> string(10) "Зенит" } var_dump( getPath( 'Купчино', 'Станция метро 3/4' ) ); // > array(0) { }
Комментарии