PHP中递归深度遍历复杂数组，提取所有关联键值数据

引言与问题描述

在php开发中，我们经常会遇到需要处理复杂数据结构的情况，其中数组的键和值之间可能存在多层级的关联，形成一个类似图（graph）的结构。例如，一个键的值可能是另一个数组的键，我们需要从一个起始键开始，递归地找出所有直接和间接关联的数值。

考虑以下PHP数组示例：

$dataArray = Array
(
    22 => Array
        (
            0 => 1074,
            1 => 1926
        ),

    1772 => Array
        (
            0 => 1080,
            1 => 1921
        ),

    1926 => Array
        (
            0 => 1772
        ),

    1080 => Array
        (
            0 => 1833
        )
);

我们的目标是从一个指定的起始键（例如 1926）开始，遍历并收集所有关联的数值。根据上述数据，1926 关联到 1772，而 1772 又关联到 1080 和 1921，1080 进一步关联到 1833。因此，期望的输出是 [1772, 1080, 1921, 1833]。

这种问题不能简单地通过单层循环解决，因为它涉及深度的递归探索。同时，为了避免无限循环（如果数据存在循环引用，例如 A -> B -> A），我们需要一种机制来跟踪已访问的键。

递归遍历核心思想

解决这类问题的最佳方法是使用递归。递归函数能够模拟深度优先搜索（DFS）的过程，从一个节点（键）开始，探索其所有子节点（值），然后对每个子节点重复这个过程。

立即学习“PHP免费学习笔记（深入）”；

为了确保遍历的正确性和效率，递归函数需要管理以下几个关键状态：

怪兽AI数字人

数字人短视频创作，数字人直播，实时驱动数字人

44

查看详情

1. 当前处理的键 (Current Key): 每次递归调用的起点。
2. 完整数据源 (Data Source): 原始的复杂数组。
3. 结果集合 (Result Set): 用于累积所有找到的关联值。
4. 已访问键集合 (Visited Keys Set): 用于记录在当前遍历路径中已经处理过的键，以防止重复处理和无限循环。

通过将结果集合和已访问键集合作为引用传递给递归函数，可以确保在整个递归过程中它们的状态是共享和更新的。

解决方案实现

下面是一个实现上述逻辑的PHP函数：

<?php

/**
 * 递归地从复杂数组中收集所有关联值
 *
 * @param int|string $startKey      当前要处理的起始键
 * @param array      $dataSource    原始的复杂数据数组
 * @param array      &$result       通过引用传递，用于累积所有找到的关联值
 * @param array      &$visitedKeys  通过引用传递，用于记录已访问的键，防止无限循环
 * @return void
 */
function collectRelatedValues(int|string $startKey, array $dataSource, array &$result, array &$visitedKeys): void
{
    // 1. 如果当前键已被访问，则直接返回，避免无限循环和重复处理
    if (isset($visitedKeys[$startKey])) {
        return;
    }

    // 2. 将当前键标记为已访问
    $visitedKeys[$startKey] = true;

    // 3. 检查当前键是否存在于数据源中，且其值是一个数组
    if (isset($dataSource[$startKey]) && is_array($dataSource[$startKey])) {
        // 4. 遍历当前键对应的所有值
        foreach ($dataSource[$startKey] as $value) {
            // 将当前值添加到结果集中
            $result[] = $value;

            // 5. 递归调用自身，以当前值作为新的起始键进行探索
            // 确保值是有效的键类型（通常是整数或字符串）
            if (is_int($value) || is_string($value)) {
                collectRelatedValues($value, $dataSource, $result, $visitedKeys);
            }
        }
    }
}

// 示例数据
$dataArray = [
    22 => [1074, 1926],
    1772 => [1080, 1921],
    1926 => [1772],
    1080 => [1833],
    // 示例：添加一个循环引用，以便测试 visitedKeys 的作用
    // 1833 => [22]
];

// 初始化结果数组和已访问键数组
$finalResult = [];
$visitedKeys = [];

// 调用函数，从键 1926 开始收集所有关联值
$startKey = 1926;
collectRelatedValues($startKey, $dataArray, $finalResult, $visitedKeys);

echo "从键 {$startKey} 开始收集到的所有关联值：\n";
print_r($finalResult);

// 预期输出:
// Array
// (
//     [0] => 1772
//     [1] => 1080
//     [2] => 1921
//     [3] => 1833
// )

?>

代码解析与注意事项

1. 函数签名: collectRelatedValues(int|string $startKey, array $dataSource, array &$result, array &$visitedKeys)

   • $startKey: 当前递归层级要处理的键，可以是整数或字符串。
   • $dataSource: 原始的完整数据数组，在整个递归过程中保持不变。
   • &$result: 这是一个通过引用传递的数组。所有找到的关联值都会被追加到这个数组中。通过引用传递，可以避免在每次递归调用时复制大型数组，提高效率。
   • &$visitedKeys: 这也是一个通过引用传递的数组，用作一个哈希集合，记录所有已经作为 startKey 被处理过的键。它的值可以是任意非空值（例如 true），关键是 isset($visitedKeys[$key]) 的快速查找。

2. 防止无限递归:if (isset($visitedKeys[$startKey])) { return; } 这是防止无限循环的关键。在处理任何键之前，我们首先检查它是否已经在 $visitedKeys 中。如果已存在，说明这个键在当前的递归路径中已经被访问过，或者在更早的路径中作为 startKey 被处理过。直接返回可以有效阻止循环引用导致的无限递归。

3. 标记已访问键:$visitedKeys[$startKey] = true; 在处理一个键之前，立即将其添加到 $visitedKeys 中。这样，即使在当前键的子节点中再次遇到它，也会被上面的检查机制捕获。

4. 数据源检查:if (isset($dataSource[$startKey]) && is_array($dataSource[$startKey])) { ... } 在尝试遍历 $dataSource[$startKey] 之前，我们首先检查该键是否存在，并且其值是否为一个数组。这确保了代码的健壮性，避免因访问不存在的键或非数组类型数据而产生错误。

5. 结果收集与递归调用:$result[] = $value;collectRelatedValues($value, $dataSource, $result, $visitedKeys); 对于当前键的所有子值，我们首先将其添加到 $result 数组中。然后，我们以这个子值作为新的 startKey，递归地调用 collectRelatedValues 函数，继续探索更深层次的关联。这里需要注意，只有当 $value 是一个有效的键类型（整数或字符串）时，才进行递归调用。

6. 性能考量:

   • 引用传递: 使用引用传递 $result 和 $visitedKeys 显著提高了性能，避免了在每次递归调用时复制大型数组的开销。
   • 哈希表查找: $visitedKeys 数组作为哈希表，isset() 操作的平均时间复杂度为 O(1)，这使得检查已访问键非常高效。
   • PHP递归深度限制: PHP默认的递归深度限制通常为 100 或 256。对于非常深的数据结构，可能会超出此限制导致栈溢出错误。在这种情况下，可以考虑将递归算法转换为迭代算法（例如，使用一个显式栈实现深度优先搜索，或使用队列实现广度优先搜索），或者增加 php.ini 中的 xdebug.max_nesting_level（如果使用 Xdebug）或 pcre.recursion_limit。

总结

通过本教程，我们学习了如何利用递归函数有效地处理PHP中复杂、图状的数组结构。核心在于通过引用传递共享状态（结果集和已访问键集），并利用“已访问”集合机制巧妙地避免了无限循环。这种方法不仅能够准确地提取所有关联数据，而且在设计上考虑了性能和健壮性，为处理类似的数据关联问题提供了通用的解决方案。理解并掌握这种递归遍历模式，对于处理各种嵌套和关联数据场景都将大有裨益。

以上就是PHP中递归深度遍历复杂数组，提取所有关联键值数据的详细内容，更多请关注php中文网其它相关文章！