php - 如何重新排列数组项，将依赖项移动到顶部？

Question

我有以下数组，其中每一项可能(或可能不依赖)另一项:

$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(),
    'b' => array(
        'depends' => 'a'
    ),
    'd' => array(
        'depends' => 'a'
    ),
    'c' => array(
        'depends' => 'b'
    ),
);

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

编辑:忘了说应该检测循环引用(b 依赖于 a 而 a 又依赖于 b 不应被允许)。

Answer 1

这叫做 topological sorting .如果您将结构视为一个图，其中“a 取决于 b”等于从顶点 b 到顶点 a 的有向边，您应该只进行拓扑排序来获得答案。

拓扑排序的实现可以这样进行:

令 graph[ n ][ n ] 为对应于您的数组的图(graph[ i ][ j ] = 1 表示 j 取决于 i)。

1. ans = {}//空序列
   
2. 收入 = 新数组[ n ]
   
3. 收入[ i ] = 到达顶点 i 的边数
   
4. used = new array[ n ]//显示是否有任何顶点已经被使用，默认全为false
   
5. while ans.size != n//还有未使用的顶点
   开始
   找到 i s.t. income[ i ] == 0 and used[ i ] == false
   ans.append( i )
   对于每个 j s.t. 图[ i ][ j ] == 1 递减 收入[ j ]
   结束
   
6. 返回答案