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

Question

我有以下array每个项目可能(或可能不依赖)另一个项目:

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

我希望移动(或制作另一个array)依赖项移动到顶部.首先a,然后b和d(都依赖a),最后c取决于b.顺序b和d不相关:

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

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

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

Answer 1

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

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

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

1. ans = {} //空序列
   
2. 收入 = 新数组 [n]
   
3. income [i] =传入顶点i的边数
   
4. used = new array [n] //显示是否已使用任何顶点,默认为false
   
5. 而 ANS .size!= N //仍有未使用的顶点
   就开始
   找我ST 收入 [I] == 0和使用的 [I] ==假
   ANS .append(我)
   每个 ĴST 图 [i] [j ] == 1 减少 收入 [j]
   结束
   
6. 返回 ans