JS中具有依赖项的可遍历树可以使用什么方法？_JavaScript

自从我不确定如何措辞以来，这可能是最糟糕的标题，但希望我可以在这里更好地解释。 请注意，这个问题中会有很多错误的用语，对此我深表歉意。

我想尝试在可以遍历依赖关系树的节点中构建JS应用程序。 通常，用jQuery遍历普通树是可以的，但是我认为这要复杂得多。

我以这张图片为例：

（从以前的图像更新，因为在某些浏览器中它重定向到了较小的分辨率）

我希望能够选择一个节点并使应用程序输出到该节点的最有效路由，包括所有依赖项。 例如，如果我想学习屏蔽技术1，它将输出：研究实验室1->研究实验室2->研究实验室3->研究实验室4->研究实验室5->研究实验室6->能源技术1 ->能源技术2->能源技术3->屏蔽技术1

在此示例中，研究实验室是优先事项，但是只要遵循两条路径，任何顺序都可以。

到目前为止，我还真的不知道如何处理它。 如果它是一个简单的树结构，没有多个依赖关系，那么我将其设置为树。

如果您有想法的话，请随时提取较小的示例。

依赖关系结构不是树，而是有或DAG：

有向的 ：边缘从一个节点到另一个节点，因此具有方向；
非循环的 ：没有循环；
图：节点可以有一个以上的传入边缘（与树不同，它们最多具有一个父节点）。

（我之所以这么说是因为DAG在各种应用程序（包括本应用程序）中都很棒并且很有用。值得您花时间学习它们。）

您要寻找的是“目标”节点中的或遍历。 （在示例图像中，您将沿着边缘向后移动。）

你想要哪一个？ 这取决于您要确定的优先级：深度优先将倾向于首先完成链（例如，如您建议的“路线”中所述，RL1-> RL2-> ...-> ET1-> ET2-> ...）广度优先将倾向于先完成“级别”（例如RL1-> ET1-> RL2-> ET2-> ...）

我绝对建议按照建议对有向图进行一些研究，并找到一种使您满意的方法。 您可能有很多不同的方法可以执行此操作，这取决于您确定首选的体系结构。

如果您只是在迷惑有向图，那么我想出了自己的“俱乐部级”解决方案，该解决方案可能没有采用最佳做法，并且在生产代码中使用时过于粗略（除非您知道自己的意思）。重新做）。 我所写的内容可能会有一些改进。 买者自负！

首先，我创建了一个数组来表示有向无环图（或“ DAG”）中的每个单独节点，并为每个节点赋予唯一的ID。 该ID与其在nodes数组中的位置相对应。

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;
}

枚举节点后，必须在节点之间建立父/子（或尾/头）关系。 我用术语“邻接”来指两个节点之间的父/子关系。 ¹

首先，我创建了一个函数，该函数将填充节点对象的Adjacencies属性-最终将根据nodes数组将其用于创建邻接矩阵。

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;
}

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

 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");

是一个二维数组，向您显示DAG中每个节点之间的每个尾巴/头部关系-一种额外的便利。 在我的实现中，如果adjacencyMatrix[0][3] === true ，则nodes[0]是nodes[3]的父级（换句话说，“研究实验室1”是“ Energy Technology 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; }

邻接矩阵完成后，我们可以递归地遍历矩阵以找到通向给定节点的每条路径。

 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填充了从“根”节点到给定节点的有序节点路径。 像[1, 3, 5]这样的路径表示， nodes[1]是nodes[3]的父级，而nodes[3]是nodes[5]的父级。

希望这会有所帮助，加油！ :)

¹ _{这可能是该术语的错误用法。}

JS中具有依赖项的可遍历树可以使用什么方法？

问题描述

1楼

2楼