Поиск пути в многомерном массиве для определенного идентификатора

Question

У меня есть массив, который хранится так:

[0] => Array
    (
        [id] => 1
        [cat_name] => c1
    )

[1] => Array
    (
        [id] => 2
        [cat_name] => c2
        [copii] => Array
            (
                [0] => Array
                    (
                        [id] => 5
                        [cat_name] => c21
                    )

                [1] => Array
                    (
                        [id] => 6
                        [cat_name] => c22
                    )

            )

    )

[2] => Array
    (
        [id] => 3
        [cat_name] => c3
        [copii] => Array
            (
                [0] => Array
                    (
                        [id] => 7
                        [cat_name] => c31
                        [copii] => Array
                            (
                                [0] => Array
                                    (
                                        [id] => 9
                                        [cat_name] => c311
                                    )

                            )

                    )

                [1] => Array
                    (
                        [id] => 8
                        [cat_name] => c32
                    )

            )

    )

Я пытаюсь найти более простой способ найти маршрут к определенному идентификатору. Теперь я использую foreach для перебора всех возможных массивов и нахождения маршрута.

Пример:

id = 1:
     route[0][id]=1,route[0][cat_name]=c1
id = 5:
    route[0][id]=2,route[0][cat_name]=c2
    route[1][id]=5,route[1][cat_name]=c21
id = 9:
    route[0][id]=3,route[0][cat_name]=c3
    route[1][id]=7,route[1][cat_name]=c31
    route[2][id]=9,route[2][cat_name]=c311

Если мой вопрос не имеет смысла, я виню его в том, что я потратил часы на то, чтобы найти хорошее решение ...

Answer 1

Вместо публикации нескольких кодов, я бы посоветовал вам прочитать рекурсию, если вы не знаете об этом. PHP не слишком хорош в рекурсии, но это действительно ваш единственный вариант.

По сути, вы вызываете функцию, которая принимает массив, идентификатор для поиска и строку / массив, представляющий путь. Сначала вызовите это с пустой строкой или пустым массивом для последнего параметра.

В функции вы бы сделали это:

• Запустить foreach через верхний уровень $array
• Если вы найдете $id, который вы ищете, верните $path.
• Если одно из значений массива является подмассивом, добавьте текущий узел ID и снова вызовите функцию с этим - что-то вроде $foundPath = findPath( $array, $id, $path ).
• Если $foundPath что-то возвращает, значит, у вас есть свой путь, и вы можете вернуться.
• Если ничего не найдено ($foundPath равно false или равно нулю, как показано ниже), оставьте его и переходите к следующей итерации цикла.
• В конце цикла, если вы ничего не нашли, верните false или null.

Надеюсь, это поможет!

Answer 2

Рекурсия - это то, что вы хотите:

<?php

    function walk_array(array $a, &$ra, $path, $depth = 0) {
     $id= isset($path[$depth]) ? $path[$depth] : null;
     if (!is_null($id)) {
      foreach ($a as $a2) {
       if ($a2['id'] == $id) {
        $ra[$depth]= $a2;
        unset($ra[$depth]['copii']);
        // This is the key bit - recursion is simply a function calling itself:
        if (isset($a2['copii']))
         walk_array($a2['copii'], $ra, $path, ++$depth);
       }
      }
     }
    }

    $complex_array= array(
      array('id'=> 1, 'name'=> 'Node #1', 'copii'=> array(
       array('id'=> 3, 'name'=> 'Node #3', 'copii'=> array(
         array('id'=> 4, 'name'=> 'Node #4')
       ))
      )),
      array('id'=> 2, 'name'=> 'Node #2', 'copii'=> array(
       array('id'=> 5, 'name'=> 'Node #5', 'copii'=> array(
         array('id'=> 6, 'name'=> 'Node #6',)
       ))
      )),
    );    

    // Prints out nodes 1,3,4 in order
    $ra= array();
    walk_array($complex_array, $ra, array(1, 3, 4));
    print_r($ra);

    // Prints out nodes 2,5,6 in order
    $ra= array();
    walk_array($complex_array, $ra, array(2, 5, 6));
    print_r($ra);

    // Prints out empty array
    $ra= array();
    walk_array($complex_array, $ra, array(5, 2, 4));
    print_r($ra);

    // Prints out nodes 2,5 in order
    $ra= array();
    walk_array($complex_array, $ra, array(2, 5));
    print_r($ra);
?>

Answer 3

Еще один способ, которым я могу придумать - избегая рекурсии, - это использовать «переменные переменные», поэтому вы просто пробуете любую возможную комбинацию индексов массива, вплоть до точки.

$search = 3;
$ind = '$arr[0][copii][1]'; // generated somehow
if ( isset(${$ind}['id']) && ${$ind}['id'] == $search ) {
  // we found it
}

Это займет столько же времени, и вы не гарантированно найдете что-нибудь. Также, когда я пишу это, я изо всех сил пытаюсь найти надежный способ генерирования значений $ind ... кроме рекурсии. Я думаю, вы могли бы сгенерировать 3-значные числа, такие как 000, 001, 002 и использовать каждый символ для создания индексов, таких как $arr[0][copii][0][copii][0], $arr[0][copii][0][copii][1] и $arr[0][copii][0][copii][2].

Этот метод все еще не совершенен, поскольку вы, несомненно, пропустите значения и будете искать множество значений, которых не существует. Честно говоря, рекурсия - это более простой и понятный вариант кода, и если в вашем массиве сотни записей, вы не заметите большой проблемы с производительностью.

Answer 4

Ваш вопрос действительно не имеет смысла. Что означает «Поиск маршрута»?

Похоже, ваш массив имеет рекурсивную структуру, описывающую граф; алгоритм обхода графа для нахождения кратчайшего пути может быть более подходящим (то есть преобразовать ваш массив в структуру данных графа - может быть, список узлов + список ребер, и запустить алгоритм на нем).