Исправлена ​​функция для вычислений на графике

Массив $nodes не настроен как неориентированный граф. На изображении показано, что так и должно быть.

$nodes = [
    'a' => ['b'],
    'b' => ['a d'],
    'c' => ['d'],
    'd' => ['b c e f'],
    'e' => ['d'],
    'f' => ['d g'],
    'g' => ['f i'],
    'h' => ['i'],
    'i' => ['g h']
];

Для print_r(findPathBetweenNodes('f', 'h', $nodes));

Array
(
    [0] => g
    [1] => i
)

Для print_r(findPathBetweenNodes('a', 'c', $nodes));

Array
(
    [0] => b
    [1] => d
)

Я согласен с Саймоном, ваша структура взаимоотношений узлов не идеальна для этой задачи. Значения, разделенные пробелами, требуют ненужной дополнительной работы и не могут быть оптимизированы для повышения производительности поиска. Вместо этого я рекомендую создать двухмерный массив поиска, поскольку PHP очень быстро ищет ключи (а не поиск значений).

В свою рекурсивную функцию я включил возможность избежать потенциальной циклической/бесконечной рекурсии путем удаления/потребления элементов из массива поиска при каждом более глубоком обходе.

Мой фрагмент не предназначен и не протестирован для работы в сценарии, в котором могут возникнуть несколько путей к узлам. Если это возможно, укажите это в тексте вопроса и предоставьте более сложные образцы данных (или задайте новый вопрос).

Чтобы отличить полные/успешные пути от несвязанных узлов, я разработал свою функцию так, чтобы она возвращала null, чтобы указать отсутствие подходящего пути.

Код: (Демо)

function findWayPoints(array $lookup, $start, $end, array $path = []): ?array
{
    if (isset($lookup[$start][$end])) {
        return $path;  // full path found; no need to further recurse
    }
    foreach ($lookup[$start] ?? [] as $conn => $irrelevant) {
        $result = findWayPoints(
            array_diff_key($lookup, [$start => null]),  // eliminate circular/infinite recursion
            $conn,  // change starting node in next call
            $end,
            array_merge($path, [$conn])  // append current match to path
        );
        if ($result !== null) {
            return $result;
        }
    }
    return null;  // dead end; kill path
}

function buildLookup($nodes) {
    $lookup = [];
    foreach ($nodes as $k => [$connections]) {
        foreach (explode(' ', $connections) as $conn) {
            $lookup[$k][$conn] = true;
            $lookup[$conn][$k] = true;
        }
    }
    return $lookup;    
}

$nodes = [
    'f' => ['d g'],
    'b' => ['a d'],
    'g' => ['i'],
    'd' => ['c e'],
    'i' => ['h']
];
$lookup = buildLookup($nodes);

   
echo json_encode(findWayPoints($lookup, 'h', 'f'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'f', 'h'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'a', 'c'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'a', 'b'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'a', 'h'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'i', 'j'));

Выход:

["i","g"]
---
["g","i"]
---
["b","d"]
---
[]
---
["b","d","f","g","i"]
---
null