我有以下数组
,其中每一项可能(或可能不依赖)另一项:
$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
不应被允许)。
最佳答案
这叫做 topological sorting .如果您将结构视为一个图,其中“a 取决于 b”等于从顶点 b 到顶点 a 的有向边,您应该只进行拓扑排序来获得答案。
拓扑排序的实现可以这样进行:
令 graph[ n ][ n ] 为对应于您的数组的图(graph[ i ][ j ] = 1 表示 j 取决于 i)。
- ans = {}//空序列
- 收入 = 新数组[ n ]
- 收入[ i ] = 到达顶点 i 的边数
- used = new array[ n ]//显示是否有任何顶点已经被使用,默认全为false
- while ans.size != n//还有未使用的顶点
开始
找到 i s.t. income[ i ] == 0 and used[ i ] == false
ans.append( i )
对于每个 j s.t. 图[ i ][ j ] == 1 递减 收入[ j ]
结束 - 返回答案
关于php - 如何重新排列数组项,将依赖项移动到顶部?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15901159/