在 JS 中有依赖关系的可遍历树可以使用什么方法？

Question

可能是有史以来最糟糕的标题，因为我不确定如何表达它，但希望我能在这里解释得更好。请注意，这个问题中会出现大量错误的术语，对此我深表歉意。

我想尝试在节点中构建一个可以遍历依赖树的 JS 应用程序。通常用 jQuery 遍历的普通树就可以了，但我认为这比那个要复杂一点。

我以这张图片为例：

https://i.imgur.com/MQHWBDk.png（根据之前的图片更新，因为在某些浏览器中它重定向到较小的分辨率）

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

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

到目前为止，我还不知道如何处理它。如果它是一个没有多重依赖的简单树结构，我会把它设置成一棵树。

如果您知道如何做，请随意提取更小的示例。

Answer 1

依赖结构不是树，而是 directed acyclic graph 或 DAG：

有向：边从一个节点到另一个节点，因此有方向；
非循环：没有循环；
graph: 节点可以有多个输入边（不像 trees，它们最多只有一个父节点）。

（我提到这一点是因为 DAG 非常棒并且在各种应用程序中都很有用，包括这个应用程序。值得您花时间了解它们。）

您正在寻找的是来自您的 "target" 节点的 depth-first or breadth-first 遍历。（在您的示例图像中，您将沿着边缘向后移动。）

你想要哪一个？这取决于您想要确定的优先级：深度优先将倾向于首先完成链（例如 RL1 -> RL2 -> ... -> ET1 -> ET2 -> ... 如您提议的 "route"），而广度优先将倾向于先完成 "levels"（例如 RL1 -> ET1 -> RL2 -> ET2 -> ...）

Answer 2

我绝对建议按照 candu 的建议对有向图进行一些研究，并找到一种您可以接受的方法来完成这项工作。您可能有很多不同的方法来执行此操作，您需要找出首选架构。

如果您只是想弄乱有向图，我想出了我自己的 "club-level" 解决方案，它可能没有采用最佳实践，并且在生产代码中使用有点过于粗略（除非你知道你在做什么）。可能可以对我所写的内容进行一些改进。 买者自负！

首先，我创建了一个数组来表示有向无环图（或 "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;
}

枚举节点后，必须建立节点之间的 parent/child（或 tail/head）关系。我使用术语 'adjacency' 来指代两个节点之间的 parent/child 关系。¹

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

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

最后，我们可以手动指定每个节点的 tail/head 关系。

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

adjacency matrix 是一个二维数组，向您显示 DAG 中每个节点之间的每个 tail/head 关系 - 有点方便。在我的实现中，如果 adjacencyMatrix[0][3] === true，那么 nodes[0] 是 nodes[3] 的父级（换句话说，"Research Lab 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 = [];

// ... e.g. 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 (i.e. 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 的数组数组，其中填充了从 "root" 节点到给定节点的有序节点路径。像 [1, 3, 5] 这样的路径意味着 nodes[1] 是 nodes[3] 的父级，而 nodes[3] 是 nodes[5].

的父级

希望这对您有所帮助，干杯！ :)

¹_{这可能是对术语的错误使用。}

在 JS 中有依赖关系的可遍历树可以使用什么方法？

What method could be used for a traversable tree with dependencies within JS?

javascript

algorithm

tree

jquery

node.js