Рекурсивная функция в PHP для поиска пути между произвольными узлами - PullRequest
Новая
       12

Рекурсивная функция в PHP для поиска пути между произвольными узлами

0 голосов
/ 14 октября 2019

У меня есть массив, представляющий соединения между узлами.

Учитывая определенный конечный узел, я хотел бы вернуть подмножество узлов, которые ведут к этому конечному узлу.

Например, еслиМои определения узлов: "ab", "ac", "ce", "ef", "ek", "kz", "qz", "xq" "km", "ct", которые представляют следующее:

Whole map

, и я хотел бы видеть пути, ведущие к 'z', которые:

  • ac,ce, ek, kz
  • qz, xq

critical path map

У меня есть PHP-код: 

<?php

$end   = "z";  
$items = array("a-b", "a-c", "c-e", "e-f", "e-k", "k-z", "q-z", "x-q", "k-m", "c-t"); 

$graph = getPre($items, $end);  

print_r($graph);  // This is what I want to populate

exit();

function getPre($array, $char) {  

  $predecessors = array_filter($array, function($line) use($char) {
      return strpos(substr($line, 2, 1), $char) === FALSE ? FALSE : TRUE;
            }
          );
  if (count($predecessors) == 0) {
    return;
  } else {
      print_r($predecessors)."<br>";
    echo "<br>";
    foreach ($predecessors as $pre) {getPre($array, substr($pre, 0,1));}
  }
}

?>

который выводит: 

Array ( [5] => k-z [6] => q-z )
Array ( [4] => e-k )
Array ( [2] => c-e )
Array ( [1] => a-c )
Array ( [7] => x-q )

который по крайней мере является правильным списком узлов, так что я почти на месте.

Вопрос : Как у меня естьрезультаты возвращены в мой массив $graph?

Где-то мне нужно return $predecessors; и объединить его с предыдущими результатами. Я также хочу добавить функциональность, чтобы можно было указывать начальный узел, но я думаю, что это будет просто дополнительный тест в моем рекурсивном конечном тесте.

1 Ответ

2 голосов
/ 14 октября 2019

Главное, что вам нужно (как вы сказали), это создать массивы для передачи данных обратно. Этот код создаст подэлемент, если есть еще элементы для добавления, или просто установите возвращаемое значение для элемента, если ничего не найдено. Не уверен, что формат вывода соответствует именно вашему, но вы можете работать с ним. 

function getPre($array, $char) {
    $graph = [];
    foreach ($array as $pre) {
        if ( $pre[2] == $char ) {
            $graph[$pre] = getPre($array, $pre[0]) ?: $pre;
        }
    }

    return $graph;
}

Обратите внимание, вместо того, чтобы использовать substr() для извлечения символа, выможет использовать строку в качестве массива, а [2] является третьим символом.

Это выводит ... 

Array
(
    [k-z] => Array
        (
            [e-k] => Array
                (
                    [c-e] => Array
                        (
                            [a-c] => a-c
                        )

                )

        )

    [q-z] => Array
        (
            [x-q] => x-q
        )

)

Чтобы вывести коды в виде строк, я обработал результатвышеуказанная функция с использованием итераторов. Идея состоит в том, чтобы начать с конечных узлов, а затем проследить (используя getSubIterator()) к основанию дерева ... 

$graph = getPre($items, $end);
$objects = new RecursiveIteratorIterator( new RecursiveArrayIterator( $graph ), RecursiveIteratorIterator::LEAVES_ONLY );
foreach ( $objects as $name => $object )    {
    $path = $object;
    for ( $depth = $objects->getDepth() - 1; $depth >= 0; $depth-- ) {
        $path .= ",".$objects->getSubIterator( $depth )->key();
    }
    echo $path.PHP_EOL;
}

Что выводит ... 

a-c,c-e,e-k,k-z
x-q,q-z
...