Работа с графами

Graph.php

<?php

/**
 * Работа с графами
 * 
 * @author sagittaracc <[email protected]>
 */
class Graph
{
    /**
     * @var array матрица смежности графа
     */
    private $structure;
    /**
     * Constructor
     * @param array $structure матрица смежности графа
     */
    function __construct($structure)
    {
        $this->structure = $structure;
    }
    /**
     * Возможные пути перемещения из текущей точки без учета точки из которой пришли
     * @param string $prev точка из которой пришли в текущую
     * @param string $curr текущая точка
     * @return array перечень возможных шагов
     */
    private function getPossibleSteps($prev, $curr)
    {
        $steps = [];

        foreach ($this->structure[$curr] as $step) {
            if ($step == $prev) continue;
            $steps[] = $step;
        }

        return $steps;
    }
    /**
     * Один шаг по направлению из текущей вершины графа в сторону конечной точки
     * @param string $prev вершина из которой пришли
     * @param string $curr текущая вершина графа
     * @param string $end конечная точка
     * @return array|null возвращает путь из текущей точки в возможную сторону по направлению к конечной точке
     * или null если перемещение невозможно
     */
    private function step($prev, $curr, $end)
    {
        if ($curr == $end) {
            return [$end];
        }
    
        if (!isset($this->structure[$curr])) {
            return null;
        }

        $possibleSteps = $this->getPossibleSteps($prev, $curr);
        if (empty($possibleSteps)) {
            return null;
        }
    
        foreach ($possibleSteps as $step) {
            $path = $this->step($curr, $step, $end);
            if ($path) {
                return array_merge([$curr], $path);
            }
        }
    
        return null;
    }
    /**
     * Построить путь из одной точки в другую
     * @param string $from начальная точка
     * @param string $to конечная точка
     * @return array массив точек пути из $from в $to
     */
    public function getPath($from, $to)
    {
        return $this->step(null, $from, $to);
    }
}

/**
 * --------------------------------------------------------
 *                         Пример:
 * --------------------------------------------------------
 * 
 * Граф выглядит следующим образом - https://ibb.co/M7gcytv
 * 
 */
$graph = new Graph([
    'C' => ['B'],
    'B' => ['A', 'C'],
    'A' => ['B', 'D', 'G', 'L'],
    'D' => ['E', 'F', 'A'],
    'E' => ['D'],
    'F' => ['D'],
    'G' => ['A', 'H', 'I'],
    'H' => ['G'],
    'I' => ['G', 'J', 'K'],
    'J' => ['I'],
    'K' => ['I'],
    'L' => ['A', 'M', 'N', 'O'],
    'M' => ['L'],
    'N' => ['L'],
    'O' => ['L'],
]);

var_dump($graph->getPath('F', 'O'));