什么方法可以用于JS内的依赖关系的遍历树?

可能是自从我不确定如何expression它以来最糟糕的标题,但希望我能在这里更好地解释。 请注意,在这个问题上会出现错误的术语,我对此表示歉意。

我想尝试在节点中构build一个可以遍历依赖的JS应用程序。 通常用jQuery遍历一棵正常的树会很好,但我认为这比这更复杂一点。

我以这个图像为例:

http://img.nodejscore.com/javascript/MQHWBDk.png (从以前的图像更新,因为在一些浏览器,它redirect到一个较小的分辨率)

我希望能够select一个节点,并让应用程序输出到该节点的最有效的路由,包括所有的依赖关系。 例如,如果我想到屏蔽技术1,它会输出:研究实验室1 – >研究实验室2 – >研究实验室3 – >研究实验室4 – >研究实验室5 – >研究实验室6 – >能源技术1 – >能源技术2 – >能源技术3 – >屏蔽技术1

在这个例子中,研究实验室是优先考虑的,但只要遵循两条途径,任何顺序都可以。

到目前为止,我还没有真正知道如何处理它。 如果它是一个没有多重依赖关系的简单的树结构,我只是将它设置为一棵树。

如果你有一个想法,请随意提取较小的例子。

       

网上收集的解决方案 "什么方法可以用于JS内的依赖关系的遍历树?"

我肯定会推荐做Candubuild议的关于有向图的研究,并find一种方法来完成这个你感觉舒服的工作。 可能有很多不同的方式可以做到这一点,这取决于你自己找出首选的架构。

如果你只是搞定了定向图,我想出了自己的“俱乐部级”解决scheme,这可能不会采用最佳实践,而且在生产代码中使用有点过于粗略(除非你知道自己的“重做)。 对我写的内容可能会有一些改进。 买者自负!

首先,我创build了一个数组来表示有向非循环图(或“DAG”)中的每个单独节点,并给每个节点一个唯一的ID。 该ID对应于其在nodesarrays中的位置。

 var nodes = []; nodes.push( { Name: "Research Lab 1", Adjacencies: [], ID: null }, { Name: "Research Lab 2", Adjacencies: [], ID: null }, { Name: "Computer Technology 1", Adjacencies: [], ID: null }, { Name: "Energy Technology 1", Adjacencies: [], ID: null }, { Name: "Combustion Drive 1", Adjacencies: [], ID: null }, { Name: "Energy Technology 2", Adjacencies: [], ID: null }, { Name: "Computer Technology 8", Adjacencies: [], ID: null }, { Name: "Impulse Drive 1", Adjacencies: [], ID: null }, { Name: "Research Lab 3", Adjacencies: [], ID: null }, { Name: "Armor Technology 1", Adjacencies: [], ID: null }); for (var i = 0; i < nodes.length; i++) { nodes[i]["ID"] = i; } 


一旦枚举节点,必须build立节点之间的父/子(或尾/头)关系。 我使用术语“邻接”来指代两个节点之间的父/子关系。 1

首先,我创build了一个函数来填充一个节点对象的Adjacencies属性 – 它最终将被用来创build一个基于nodes数组的邻接matrix。

 Array.prototype.addAdjacency = function (tail, head) { var thisNode = findNode(tail); thisNode["Adjacencies"].push(findNode(head).Name); } // This will return the node object with a given name: function findNode(name) { return $.grep(nodes, function (n) { return n.Name == name })[0]; } 

最后,我们可以手动指定每个节点的尾部/头部关系。

 nodes.addAdjacency("Research Lab 1", "Research Lab 2"); nodes.addAdjacency("Research Lab 1", "Computer Technology 1"); nodes.addAdjacency("Research Lab 1", "Energy Technology 1"); nodes.addAdjacency("Research Lab 2", "Impulse Drive 1"); nodes.addAdjacency("Research Lab 2", "Research Lab 3"); nodes.addAdjacency("Research Lab 2", "Armor Technology 1"); nodes.addAdjacency("Computer Technology 1", "Computer Technology 8"); nodes.addAdjacency("Computer Technology 1", "Impulse Drive 1"); nodes.addAdjacency("Energy Technology 1", "Combustion Drive 1"); nodes.addAdjacency("Energy Technology 1", "Energy Technology 2"); nodes.addAdjacency("Energy Technology 1", "Impulse Drive 1"); 

邻接matrix是一个二维数组,它显示了DAG中每个节点之间的每个尾/头关系 – 增加了方便性。 在我的实现中,如果adjacencyMatrix[0][3] === true ,则nodes[0]nodes[3]的父nodes[3] (换句话说,“研究实验1”是“能源技术1”的父节点) 。

 function isAdjacent(tail, head) { return tail["Adjacencies"].indexOf(head.Name) != -1; } var adjacencyMatrix = populateAdjacencyMatrix(nodes); function populateAdjacencyMatrix(vertices) { var matrix = new Array(vertices.length); for (var i = 0; i < vertices.length; i++) { matrix[i] = new Array(vertices.length); } for (var i = 0; i < matrix.length; i++) { for (var j = 0; j < matrix.length; j++) { if (isAdjacent(vertices[i], vertices[j])) { matrix[i][j] = true; } else { matrix[i][j] = false; } } } return matrix; } 

一旦邻接matrix完成,我们就可以recursion遍历matrix来find每个通往给定节点的path。

 var pathsToNode = []; // ... eg the node at index 7, or "Impulse Drive 1": findPathTo(nodes[7], []); function findPathTo(node, path) { var nodeID = node["ID"]; var parentNodeIndices = []; var currentNodeIsRootNode = true; // A new array based off of the path argument needs to be created, or else things get a little wacky with the scope. var currentPath = new Array(); for (var i = 0; i < path.length; i++) { currentPath.push(path[i]); } // Next, add the node in this context to the 'current path'. currentPath.unshift(nodeID); // Note that if there are no paths leading up to this node, then it's the first node in the directed path. for (var i = 0; i < adjacencyMatrix[0].length; i++) { var matrixValue = adjacencyMatrix[i][nodeID]; if (matrixValue === true) { currentNodeIsRootNode = false; parentNodeIndices.push(i); } } // Finally, if the node in /this/ recursive context is a "root" node (ie it has no parents), // then add the entire path to the list of paths to the original node. if (currentNodeIsRootNode) { //console.log(" "); //console.log("Adding path to paths array:") //console.log(currentPath); //console.log("This is now what the paths array looks like:") //console.log(pathsToNode); pathsToNode.push(currentPath); } else { // Otherwise, get all of the indices of the 'parent' nodes (relative to the node in this recursive context), // and recursively find the parent nodes of each. //console.log(" "); //console.log("Recursing findPathTo function. Next nodes:") //console.log(nextNodeIndices); //console.log("Current path:") //console.log(currentPath); for (var i = 0; i < parentNodeIndices.length; i++) { findPathTo(nodes[parentNodeIndices[i]], currentPath); } } } console.log(pathsToNode); 

最后,给定nodes[7] ,我们有一个称为pathsToNode的数组数组, pathsToNode填充了从“根”节点到给定节点的有序节点path。 像[1, 3, 5]这样的path意味着nodes[1]nodes[3]的父nodes[3]nodes[3]nodes[5]的父nodes[5]

希望这有助于,欢呼! 🙂

1 这可能是一个不正确的用法。

依赖结构不是一棵树,它是一个有向非循环图 ,或DAG:

  • 指挥 :边缘从一个节点到另一个节点,从而有方向;
  • 非循环的 :没有循环;
  • :节点可以有多于一个传入边(不同于 ,最多只有一个父节点)。

(我之所以提到这个,是因为DAG在各种应用程序中都很棒并且非常有用,包括这个应用程序,值得您花时间去了解它们。)

你要找的是从“目标”节点开始的深度优先或宽度优先遍历。 (在您的示例图像中,您将沿着边缘向后移动。)

你想要哪一个? 这取决于你想要优先考虑什么:深度优先将倾向于首先完成链(例如RL1→RL2→ET1→ET2→…,如同在你提出的“路线”中)宽度优先倾向于首先完成“等级”(例如,RL1→ET1→RL2→ET2→…)