我有一個節點串列及其要求（即祖先）。好訊息是，串列保證是“順序”的（其中順序意味著沒有節點會在串列中，直到它的要求也在串列中），但我想把它放到“層次結構”中，所以我可以并行處理同一級別的節點。
例如，我有
------ ----------------
| Node | Requires |
------ ----------------
| A | |
------ ----------------
| B | |
------ ----------------
| C | A,B |
------ ----------------
| D | C |
------ ----------------
| E | |
------ ----------------
| F | E |
------ ----------------
...
我想要的是
--- ----------
| 0 | A,B,E |
--- ----------
| 1 | C,F |
--- ----------
| 2 | D |
--- ----------
...
我從第 3 方庫中獲取資料，它的傳入方式是節點的有序串列是一個字串陣列（$nodes），并且依賴項作為具有節點鍵的陣列存盤在另一個物件中名稱 ( $foreign_obj->reqs[ <node> ]->reqs)。
編輯：根據評論插入：
這是var_export這兩個專案中的一個：
節點：
array ( 0 => 'A', 1 => 'B', 2 => 'C', 3 => 'D', 4 => 'E', 5 => 'F', 6 => 'G', 7 => 'H', )
foreign_obj->reqs 的前幾個條目：
array ( 'A' => _Requirement::__set_state((array( 'name' => 'A', 'src' => '/path/to/A.js', deps => array ( ), )), 'B' => _Requirement::__set_state((array( 'name' => 'B', 'src' => '/path/to/B.js', deps => array ( ), )), 'C' => _Requirement::__set_state((array( 'name' => 'C', 'src' => '/path/to/C.js', deps => array ( 0 => 'A', 1 => 'B', ), )),
...
我可以在這里找到的所有其他問題都與您有一個已知的單一父級（例如，Flat PHP Array to Hierarchy Tree）或您至少已經知道父級（例如，PHP 分層陣列）的情況類似- 父母和孩子）。我在這里面臨的挑戰是資料是另一個方向（即，我有給定的葉子和它們的祖先）。
我可以使用類似graphp/graph的東西，但這似乎有點矯枉過正。特別是，鑒于串列已經井井有條，我希望我可以在這里做一個相當簡單的迭代，它甚至可能不需要遞回。
我認為像這樣簡單的事情會起作用：
$hierarchy = array();
foreach ( $nodes as $node ) {
$requirements = $foreign_obj->reqs[ $node ]->reqs;
if ( ! is_array( $requirements ) || empty( $requirements ) ) {
array_push($hierarchy[0], $node);
continue;
}
$index = 0;
foreach ($requirements as $req) {
<find req in $hierarchy>
if (<index of heirarchy where found> > $index) {
$index = <index of heirarchy where found>
}
}
array_push( $hierarchy[ $index 1], $node);
}
那么，這兩個問題是：
- 從邏輯上講，以上看起來是否可行，還是我錯過了一些極端情況？
- 最有效/最優雅的 PHP 方式是什么
<find req in $hierarchy>？
uj5u.com熱心網友回復：
我不知道這是否是最有效/最優雅的方法，所以我不會將我自己的答案標記為正確，看看是否有人對以下內容有任何改進，但這似乎有效：
$hierarchy = array();
foreach ( $nodes as $node ) {
$requirements = $foreign_obj->reqs[ $node ]->reqs;
if ( ! is_array( $requirements ) || empty( $requirements ) ) {
$hierarchy[0][] = $node;
continue;
}
$index = 0;
foreach ($requirements as $req) {
$i = array_key_last( array_filter($hierarchy,
fn($arr)=> in_array($req, $arr, true));
if ($i > $index) {
$index = $I;
}
}
$hierarchy[ $index 1] = $node;
}
uj5u.com熱心網友回復：
這里的想法是將節點推送到沒有要求的陣列中，然后從字典的每個鍵的值中洗掉那些新推送的元素。重復直到字典變空。
將沒有要求的節點推送到陣列1（該陣列將保存特定級別的節點）。
推送所有沒有要求的節點后，將該陣列推送到全域陣列（該陣列將保存每個級別的陣列）。
從字典中每個條目的值中洗掉那些最近推送的節點。
空陣列1。
重復。
$arr = array(); foreach ( $nodes as $node ) { $requirements = $foreign_obj->reqs[ $node ]->reqs; $arr[$node] = $requirements; } $hierarchy = array(); $level = 0; $iterations = count($arr); for($i=0; $i < $iterations; $i ){ $pushed_nodes = push_nodes($arr); $hierarchy[$level] = $pushed_nodes; $level = $level 1; $arr = delete_nodes($arr, $pushed_nodes); if (count($arr) == 0){ break; } } print_r($hierarchy); function push_nodes($arr){ $arr1 = array(); foreach ( $arr as $node => $requirements ){ if (count($requirements) == 0){ array_push($arr1, $node); } } return $arr1; } function delete_nodes($arr, $nodes_to_delete){ $arr1 = array(); foreach ( $arr as $node => $requirements ){ $new_requirements = array(); foreach ($requirements as $r ){ if ( ! in_array($r, $nodes_to_delete) ){ array_push($new_requirements, $r); } } if (count($requirements) != 0){ $arr1[$node] = $new_requirements; } } return $arr1; }
對此進行了測驗：
$arr = array(
'A' => array(),
'B' => array('A'),
'C' => array('B', 'A'),
'D' => array('B', 'A')
);
輸出 ：
Array ( [0] => Array ( [0] => A ) [1] => Array ( [0] => B ) [2] => Array ( [0] => C [1] => D ) )
uj5u.com熱心網友回復：
- 好訊息是，串列保證“有序”（其中 order 意味著在其要求也在串列中之前，沒有節點會在串列中），
好的，很好，所以這大大簡化了這個要求。正如您所說的那樣，這里不需要遞回。
- 從邏輯上講，以上看起來是否可行，還是我錯過了一些極端情況？
雖然這對我來說不是很明顯，因為宣告、賦值等似乎缺少一些變數，但是是的，從邏輯上講，你在演算法步驟方面走在了正確的軌道上。
- 執行 <find req in $hierarchy> 位的最有效/優雅的 PHP 方法是什么？
這很容易。當你完全處理一個節點及其依賴項時，將它的等級/級別存盤在另一個關聯陣列中（更正式地像一個 HashMap）。因此，現在您可以重用此映射來快速決定依賴節點級別。
片段：
<?php
$hierarchy = [];
$p_rank = [];
foreach ( $nodes as $node => $dependencies ) {
$level = 0; //$foreign_obj->reqs[ $node ]->reqs;
foreach($dependencies as $parent_node){
$level = max($level, $p_rank[ $parent_node ] 1);
}
$hierarchy[ $level ] = $hierarchy[ $level ] ?? [];
$hierarchy[ $level ][] = $node;
$p_rank[ $node ] = $level; // record the rank for use( if in case this is a dependency for some other future node)
}
print_r($hierarchy);
在線演示
注意：不幸的是，我無法復制您var_export的示例輸入，因為我沒有Requirement類定義（如果我愿意，則需要額外的作業）。我使用的示例輸入足以復制您機器上的內容。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/489408.html
上一篇：陣列重排序演算法