PHP如何编写递归函数实现基于共有用户关联的账户分组

实现逻辑 #

这个需求属于连通分量分组场景，核心是通过共有用户的传递规则把关联账户归为同一组，我们通过「用户-账户反向映射」+「递归遍历关联账户」+「访问标记」的方式实现：

• 先构建用户到所属账户的反向映射，避免每次遍历全量账户匹配用户
• 用标记数组记录已分组的账户，避免重复统计
• 递归遍历当前账户的所有关联用户下的所有未分组账户，全部加入当前分组

完整代码 #

function groupAccounts(array $input): array
{
    // 构建用户 => 所属所有账户的反向映射
    $userToAccounts = [];
    foreach ($input as $accountId => $users) {
        foreach ($users as $userId) {
            $userToAccounts[$userId][] = $accountId;
        }
    }

    $visited = []; // 记录已分组的账户
    $groups = [];  // 最终分组结果

    // 递归遍历关联账户的内部函数
    $findRelatedAccounts = function (string $currentAccount, array &$currentGroup) use (&$findRelatedAccounts, &$input, &$userToAccounts, &$visited) {
        // 已经访问过直接跳过
        if (isset($visited[$currentAccount])) {
            return;
        }
        // 标记为已访问，加入当前分组
        $visited[$currentAccount] = true;
        $currentGroup[] = $currentAccount;
        // 遍历当前账户下的所有用户
        foreach ($input[$currentAccount] as $userId) {
            // 遍历该用户关联的所有账户
            foreach ($userToAccounts[$userId] as $relatedAccount) {
                // 递归找关联账户的其他关联
                $findRelatedAccounts($relatedAccount, $currentGroup);
            }
        }
    };

    // 遍历所有账户生成分组
    foreach ($input as $accountId => $users) {
        if (!isset($visited[$accountId])) {
            $currentGroup = [];
            $findRelatedAccounts($accountId, $currentGroup);
            $groups[] = $currentGroup;
        }
    }

    return $groups;
}

// 测试用例
$input = [
    'account1_id' => ['user1_id', 'user2_id'],
    'account2_id' => ['user2_id', 'user8_id'],
    'account4_id' => ['user15_id', 'user16_id'],
    'account5_id' => ['user15_id', 'user16_id'],
    'account7_id' => ['user24_id', 'user25_id', 'user26_id', 'user27_id'],
    'account8_id' => ['user29_id', 'user30_id', 'user8_id'],
];

$result = groupAccounts($input);
print_r($result);

输出验证 #

运行上述代码输出结果和要求完全一致：

Array
(
    [0] => Array
        (
            [0] => account1_id
            [1] => account2_id
            [2] => account8_id
        )

    [1] => Array
        (
            [0] => account4_id
            [1] => account5_id
        )

    [2] => Array
        (
            [0] => account7_id
        )

)

内容的提问来源于stack exchange，提问作者niko745