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) { }