JavaScript的 - - 圖遍歷從起始節點

Question

我有看起來像這樣的圖表會按順序（最近第一）節點（例如「B」）將以最接近開始點優先的方式遍歷圖形。例如對於B，它會得到孩子D，F，然後是根，然後是兄弟B，C，然後是G，然後是B和C的孩子，等等。

即使只是有算法將被罰款

PS：我知道我可以在那裏使用Dijkstra算法，但我真的不知道如何

Answer 1

可以使用Breadth-first search實現例如here。如果樹中的邊具有與它們相關的權重，則需要Dijkstra的算法。

由於您沒有將父項保留在節點對象中，因此您需要添加預處理步驟以將父項字段添加到所有節點。這是需要的，以便在B開始時，您知道要訪問根目錄。這可以通過簡單的遍歷來完成。

廣度優先搜索保持您需要在隊列中訪問的節點。新節點添加到隊列的末尾。該算法從隊列的前端挑選新的節點進行訪問。

但要小心，因爲如果允許修改節點，隊列會變得非常大。

Answer 2

由於有關使用廣度優先算法交易所cyon建議，我想出了這個 （基於http://java.dzone.com/articles/algorithm-week-graph-breadth）：

var graph = { 
    A : [B, C], 
    B : [A, D], 
    C : [A, D], 
    D : [A, C ,E], 
    E : [B, F], 
    F : [E] 
}; 

function init (visited, graph) 
{ 
    for (var key in graph) { 
     var vertex = graph[key]; 
     visited[key] = false; 
    } 
} 

function breadthFirst (graph, start, visited) 
{ 
    // Create an empty queue 
    var queue = []; 

    // Initially enqueue only the starting vertex 
    queue.push(start); 

    //Set the starting vertex to visited 
    visited[start] = true; 

    //Add it to the result 
    result.push(start); 

    //While there is still remaining vertexes in queue 
    while (queue.length > 0) { 

     //Remove first vertex from queue and save it in "t" 
     var currentVertexID = queue.shift(); 

     //For each key in graph at "t" 
     var currentVertex = graph[currentVertexID]; 
     for (var key in currentVertex) { 

     var target = currentVertex[key]; 

      //If it has not been visited yet 
      if (!visited[target]) { 

       //Mark it as visited 
       visited[target] = true; 

       //Add it to queue 
       queue.push(target); 

       //Save it in result 
       result.push(target); 
       //console.log(result); 
      } 
     } 
    } 
} 

var result = []; 
var visited = []; 
init(visited, graph); 
breadthFirst(graph, 2, visited);  
console.log(result);  

而且因爲我做了一個分開的根，只有父母子女關係，在我的圖（因爲我是從樹上遷移而來的），所以在使用寬度之前，我必須建立一個完整的關係矩陣（以便它可以查找父母）。

我發佈它，因爲它可以爲了一棵樹第一次使用廣度進行預處理是有用

generateNodesAdjacencyMatrix : function(){ 
      var adjacencyMatrix = {}; 
      function recursiveFindNestedAndSaveLinks(parentKey, childrenKeys){ 
       //Add the links to parent pointing to his children 
       if(!_.isArray(adjacencyMatrix[parentKey])){ 
        adjacencyMatrix[parentKey] = []; 
       } 
       adjacencyMatrix[parentKey] = adjacencyMatrix[parentKey].concat(childrenKeys); 

       //For each children 
       _.each(childrenKeys, function (childKey){ 
        //Add a link to parent 
        if(!_.isArray(adjacencyMatrix[childKey])){ 
         adjacencyMatrix[childKey] = []; 
        } 
        adjacencyMatrix[childKey].push(parentKey); 

        //If it has children as well, do recursive on him 
        var child = childs[childKey]; 
        if(!_.isUndefined(child) && !_.isUndefined(child.children)){ 
         recursiveFindNestedAndSaveLinks(childKey, child.children); 
        } 
       }, this); 
      } 
      recursiveFindNestedAndSaveLinks('root', root.children); 
      return adjacencyMatrix; 
     },