자바 스크립트 종속성 목록

Question

종속성을 파악할 필요가있는 요소 목록이 있습니다.

나는이 :

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

a이 c 및 e에 b 및 d 및 d에 따라된다. 거기에 영리한 방법으로 의존성을 구성 할 수있는 방법이 있습니까? 출력은 일 (수)해야합니다

["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 스택을 사용하여 오류를 감지 할 수 있습니다. 자식이 부모로부터 다시 입력 된 경우 원형 종속성이 있습니다.

더 나은 솔루션은 표준 위상 정렬 알고리즘을 사용하는 것입니다 : 분류되지 않은 노드가 있지만, 어떤 해결되지 않은 종속성이 없습니다 하나를 선택 :

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/