萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 計算多維數組深度的遞歸算法實現

問題定義

數組深度定義為嵌套層數。例如:

$arr = array(
    array(array(1,3,4), array(array(1,2,3))),
    array(array(1,2), array(1))
);
// 深度 = 5(最深路徑:第1元素 → 第2元素 → 第1元素 → 第1元素 → 值)

遞歸算法實現

<?php
function array_depth($array) {
    $max_depth = 1; // 至少為1(當前層)
    foreach ($array as $value) {
        if (is_array($value)) {
            $depth = array_depth($value) + 1; // 子數組深度 + 當前層
            if ($depth > $max_depth) {
                $max_depth = $depth;
            }
        }
    }
    return $max_depth;
}

// 測試
$array = array(
    array("11"),
    array(),
    array(array(array("5", "6"), "7", "8")),
    array(array(array("5", "6"), "7", "8")),
    "9", "10"
);
echo array_depth($array); // 輸出 4
?>

算法分析

  • 時間複雜度:O(N),N 為所有元素總數(含子數組元素)。每個元素訪問一次。
  • 空間複雜度:O(D),D 為最大深度,遞歸調用棧深度。
  • 邊界情況:空數組深度為 1;非數組輸入可拋異常或返回 0。

非遞歸實現(棧模擬,避免棧溢出)

function array_depth_iterative($array) {
    if (!is_array($array)) return 0;
    $maxDepth = 0;
    $stack = array(array('arr' => $array, 'depth' => 1));
    while (!empty($stack)) {
        $node = array_pop($stack);
        $maxDepth = max($maxDepth, $node['depth']);
        foreach ($node['arr'] as $value) {
            if (is_array($value)) {
                $stack[] = array('arr' => $value, 'depth' => $node['depth'] + 1);
            }
        }
    }
    return $maxDepth;
}

應用場景

  • JSON 數據結構深度驗證(防止過深導致解析器棧溢出)。
  • 模板引擎限制嵌套層級。
  • 數據清洗:展平過深結構。
  • 遞歸函數安全性檢查(設置最大深度限制)。

擴展:獲取最大深度路徑

function array_depth_path($array, $currentPath = array(), &$maxDepth = 0, &$maxPath = array()) {
    $depth = count($currentPath) + 1;
    if ($depth > $maxDepth) {
        $maxDepth = $depth;
        $maxPath = $currentPath;
    }
    foreach ($array as $key => $value) {
        if (is_array($value)) {
            array_depth_path($value, array_merge($currentPath, array($key)), $maxDepth, $maxPath);
        }
    }
    return array('depth' => $maxDepth, 'path' => $maxPath);
}
copyright © 萬盛學電腦網 all rights reserved