Javascript依賴列表

Question

我有一個元素列表，我需要找出依賴關係。

我：

[{ 
    "a": ["b", "d"] 
}, { 
    "d": ["c", "e"] 
}] 

a取決於b和d和d上c和e。有沒有辦法以這種巧妙的方式構建依賴關係？輸出應該（可能）是：

["b", "c", "e", "d", "a"] 

/克里斯蒂安

Answer 1

假設你想要一個元素的遞歸依賴性，包括元素本身的列表，以任何順序：

「爲每個依賴，將它的依賴添加到依賴列表「足夠聰明瞭嗎？

function recursiveDependencies (dependencies, element){ 
    var output = [element]; 
    for(i=0; i<output.length(); i++){ 
    dependencies[output[i]].forEach(function(x){ 
     if(output.indexOf(x)<0){ //prevent duplicates 
     output.push(x) 
     } 
    }) 
    } 
    return output; 
} 

如果你想結束而不是開始元素本身，您可以修復與output.push(output.shift())

---

如果你想以這樣的順序你的依賴，每一個元素之前的元素依賴於它，那麼你將不得不定義如何處理循環依賴。處理該問題的一種方法是檢測循環依賴性並失敗。

如果最多由一個元件需要每依賴性，然後就可以使用前面的算法：簡單地讀取向後的輸出（或反向陣列或使用unshift代替push（警告：性能下降））

---

依賴關係形成一個圖，並且您正在尋找它的拓撲排序。一種（無效的）方法是按照深度優先的順序對節點進行排序，如果它們重新進入，則重新插入它們。你可以使用Open stack來檢測錯誤 - 如果一個孩子從其父母重新進入，那麼你有一個循環依賴。

一個更好的解決辦法是使用標準的拓撲排序算法：雖然有無序的節點，挑選一個沒有未解決的依賴性：

function recursiveDependencies (dependencies, root){ 
    var nodes={}; 
    var nodeCount=0; 
    var ready=[]; 
    var output=[]; 

    // build the graph 
    function add(element){ 
    nodeCount++; 
    nodes[element]={needs:[], neededBy:[], name: element}; 
    if(dependencies[element]){ 
     dependencies[element].forEach(function(dependency){ 
     if(!nodes[dependency]) add(dependency); 
     nodes[element].needs.push(nodes[dependency]); 
     nodes[dependency].neededBy.push(nodes[element]); 
     }); 
    } 
    if(!nodes[element].needs.length) ready.push(nodes[element]); 
    } 

    if(root){ 
    add(root) 
    } else { 
    for (element in dependencies){ 
     if(!nodes[element]) add(element); 
    } 
    } 


    //sort the graph 
    while(ready.length){ 
    var dependency = ready.pop(); 
    output.push(dependency.name); 
    dependency.neededBy.forEach(function(element){ 
     element.needs = element.needs.filter(function(x){return x!=dependency}) 
     if(!element.needs.length) ready.push(element) 
    }) 
    } 

    //error-check 
    if(output.length != nodeCount){ 
    throw "circular dependency detected" 
    } 

    return output; 
} 

小提琴：http://jsfiddle.net/Xq5dz/4/