php – 如何重新排列移动依赖项的数组项？

发布时间：2020-12-13 22:37:29 所属栏目：PHP教程来源：网络整理

导读：我有以下数组,其中每个项目可能(或可能不依赖)另一个项目： $test = array( 'c' = array( 'depends' = 'b' ),'a' = array(),'b' = array( 'depends' = 'a' ),'d' = array( 'depends' = 'a' ),); 我希望移动(或创建另一个数组)依赖项移动到顶部.首先是a,然后

我有以下数组,其中每个项目可能(或可能不依赖)另一个项目：

$test = array(
    'c' => array(
        'depends' => 'b'
    ),'a' => array(),'b' => array(
        'depends' => 'a'
    ),'d' => array(
        'depends' => 'a'
    ),);

我希望移动(或创建另一个数组)依赖项移动到顶部.首先是a,然后是b和d(都取决于a),最后是c,这取决于b. b和d的顺序无关紧要：

$rearranged = array(
    'a' => array(),'c' => array(
        'depends' => 'b'
    ),);

我很确定这是一个非常常见的情况,在重新发明轮子和浪费时间之前,我想知道是否有任何数据结构可以帮我完成工作.

编辑：忘了说应该检测循环引用(b取决于不应该允许的依赖于b的循环引用).

这称为 topological sorting.如果您将结构视为图形,其中“a取决于b”等于从顶点b到顶点a的有向边,您应该进行拓扑排序以获得答案.

拓扑排序的实现可以这样完成：

let graph [n] [n]是对应于你的数组的图形(graph [i] [j] = 1表示j取决于i).

> ans = {} //空序列> income = new array [n]> income [i] =传入顶点i的边数> used = new array [n] //显示是否已使用任何顶点,默认全部为false>而ans.size！= n //仍有未使用的顶点一开始找到我的. income [i] == 0并使用[i] == falseans.append(i)每个j s.t. graph [i] [j] == 1递减收入[j]结束>返回ans

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!