我有以下数组,其中每个项目可能(或可能不依赖)另一个项目：
$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
