查找数组中的所有后代

Question

乍一看很简单，但当我尝试解决它时，我感到很困惑。

我有 PHP 数组，其中键是前 parent 个 ID，值是 child 个 ID。一些 child ID 有自己的 children。那children可能有自己的children等等。我的目标是获得一个新数组，其中所有排名靠前的 parent ID 都有其所有级别的所有后代（children、grandchildren、曾祖父children 和依此类推）。

<?php 
// Source array 
$source = array(
    '24' => array(
        '23',
        '22'
    ),
    '25' => false,
    '22' => array(
        '21'
    ),
    '21' => array(
        '20'
    ),
    '20' => array(
        '19'
    ),
    '19' => array(
        '18'
    ),
    '18' => array(
        '17'
    )
);

// Result array I need to achieve
$result = array(
    '24' => array(
        '23',
        '22',
        '21',
        '20',
        '19',
        '18',
        '17'
    ),
    '22' => array(
        '21',
        '20',
        '19',
        '18',
        '17'
    ),
    '21' => array(
        '20',
        '19',
        '18',
        '17'
    ),
    '20' => array(
        '19',
        '18',
        '17'
    ),
    '19' => array(
        '18',
        '17'
    ),
    '18' => array(
        '17'
    )
);


?>

接下来是我的尝试：

<?php 

function get_all_descendants($source)
{
    $result = $source;
    foreach ($source as $parent_id => $children) {
        foreach ($children as $op) {
            if (isset($source[$op])) {
                foreach ($source[$op] as $bottom_level_id) {
                    $result[$parent_id][] = $bottom_level_id;
                }
            }
        }
    }

    return $result;
}

var_dump( get_all_descendants( $source ) );

array(7) {
  [24]=>
  array(3) {
    [0]=>
    string(2) "23"
    [1]=>
    string(2) "22"
    [2]=>
    string(2) "21"
  }
  [25]=>
  bool(false)
  [22]=>
  array(2) {
    [0]=>
    string(2) "21"
    [1]=>
    string(2) "20"
  }
  [21]=>
  array(2) {
    [0]=>
    string(2) "20"
    [1]=>
    string(2) "19"
  }
  [20]=>
  array(2) {
    [0]=>
    string(2) "19"
    [1]=>
    string(2) "18"
  }
  [19]=>
  array(2) {
    [0]=>
    string(2) "18"
    [1]=>
    string(2) "17"
  }
  [18]=>
  array(1) {
    [0]=>
    string(2) "17"
  }
}

?>

但是这个函数并没有找到所有的后代，看起来应该是递归的，但是我想不出怎么写。一般来说，我过去用递归写过不同的函数，但在这种情况下我打破了我的想法)

Answer 1

您可以使用堆栈或递归，然后深度优先探索结构：

<?php

function find_all_descendents($arr) {
    $all_results = [];

    foreach ($arr as $k => $v) {
        $curr_result = [];
        
        for ($stack = [$k]; count($stack);) {
            $el = array_pop($stack);

            if (array_key_exists($el, $arr) && is_array($arr[$el])) {
                foreach ($arr[$el] as $child) {
                    $curr_result []= $child;
                    $stack []= $child;
                }
            }
        }

        if (count($curr_result)) {
            $all_results[$k] = $curr_result;
        }
    }

    return $all_results;
}

$source = [
    '24' => ['23', '22'],
    '25' => false,
    '22' => ['21'],
    '21' => ['20'],
    '20' => ['19'],
    '19' => ['18'],
    '18' => ['17']
];
var_dump(find_all_descendents($source));

查找数组中的所有后代

Find all descendants in array

php

arrays

recursion

descendant