Как сгруппировать набор parent-> children, где child также может быть родительским.Имейте решение, но ищите более эффективный алгоритм

Question

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

    $parents= array(
        '1' => array(
            '2' => 'none',
            '3' => 'none',
            '9' => 'none'
        ),  
        '2' => array(
            '4' => 'none',
            '5' => 'none'
        ),  
        '6' => array(
            '7' => 'none',
            '8' => 'none',
            '9' => 'none'
        ),  
        '10' => array(
            '11' => 'none',
            '12' => 'none'
        )
    );

    $groups = array();
    foreach($parents as $parent => $children){
        foreach(array_keys($children) as $child){
            $parentgroup = -1; 
            $childgroup = -1; 
            foreach($groups as $key => $group){
                if(isset($group[$parent])){
                    $parentgroup = $key;
                }   
                if(isset($group[$child])){
                    $childgroup = $key;
                }
            }

            if($parentgroup == -1 && $childgroup == -1){
                $groups[] = array($parent => true, $child => true);
            }
            else {
                if($childgroup == -1){
                    $groups[$parentgroup][$child] = true;
                } else if($parentgroup == -1){
                    $groups[$childgroup][$parent] = true;
                } else if($parentgroup != $childgroup){
                    foreach($groups[$childgroup] as $val => $none){
                        $groups[$parentgroup][$val] = true;
                    }
                    unset($groups[$childgroup]);
                }
            }
        }
    }
    print_r($groups);

    // Result
    Array
    (
        [1] => Array
            (
                [6] => 1
                [7] => 1
                [8] => 1
                [1] => 1
                [2] => 1
                [3] => 1
                [9] => 1
                [4] => 1
                [5] => 1
            )

        [2] => Array
            (
                [10] => 1
                [11] => 1
                [12] => 1
            )

    )

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

    function BGR($users, $group){
        global $pass1;
        foreach ($users as $id => $none){
            $group[$id]++;
            if(isset($pass1[$id])){
                $children = $pass1[$id];
                unset($pass1[$id]);
                $group = BGR($children, $group);
            }
        }
        return $group;
    }

    $groups = array();
    while($pass1){
        $id = key($pass1);
        $parent = $pass1[$id];
        unset($pass1[$id]);
        $groups[] = BGR($parent, array( $id => 1));
    }
    print_r($groups);

Answer 1

Похоже, мы нашли решение для второго блока выше, которое, похоже, сокращает время обработки примерно на 20%. Оказывается, что метод был правильным, но данные должны были быть в лучшем месте. Мы могли бы сначала отформатировать данные, чтобы они выглядели примерно так:

    $parents= array(
        '1' => array(
            '2' => 'none',
            '3' => 'none',
            '9' => 'none'
        ),  
        '2' => array(
            '1' => 'none',
            '3' => 'none',
            '9' => 'none',
            '4' => 'none',
            '5' => 'none'
        ),
        '3' => array(
            '1' => 'none',
            '2' => 'none',
            '9' => 'none'
        ),
        '4' => array(
            '2' => 'none',
            '5' => 'none'
        ),
        '5' => array(
            '2' => 'none',
            '4' => 'none'
        ),
        '6' => array(
            '7' => 'none',
            '8' => 'none',
            '9' => 'none'
        ),  
        '7' => array(
            '6' => 'none',
            '8' => 'none',
            '9' => 'none'
        ),  
        '8' => array(
            '6' => 'none',
            '7' => 'none',
            '9' => 'none'
        ),  
        '9' => array(
            '6' => 'none',
            '7' => 'none',
            '8' => 'none'
        ),  
        '10' => array(
            '11' => 'none',
            '12' => 'none'
        ),  
        '11' => array(
            '10' => 'none',
            '12' => 'none'
        ),  
        '12' => array(
            '10' => 'none',
            '11' => 'none'
        )
    );

Или мы могли бы пройти данные в их текущем состоянии и привести их в состояние, в котором мы можем рекурсивно просмотреть их, и коснуться всех точек:

    $pass2 = array();
    foreach ($pass1 as $parent => $children){
        foreach($children as $child => $none){
            $pass2[$parent][$child] = true;
            $pass2[$child][$parent] = true;
        }   
    }