javascript - 查找层次结构中最长链的长度

Question

我有分层数据用于在我的应用程序中创建 svg。我需要找到该数据源中最长链的长度。我可以逐级浏览数据源，递归地深入读取 _children，调用递归函数来计算级别，但我确信一定有更好的方法。这更加复杂，因为数据源可以从它以 _children 和 _parents 开始的节点双向移动。

var findChildren = function (ds, level) {
    if (!ds._children || ds._children.length == 0) {
        return level;
    }

    var longest = level + 1;
    ds._children.forEach(function (item) {
        var result = findChildren(item, level + 1);
        if (result > longest) {
            longest = result;
        }
    });
    return longest;
}

这是我当前正在使用的函数，与检查 ds._parents 的函数相同。走另一条路，将一个的结果作为另一个的起始级别。我确信一定有更好的方法......

例如，相同的数据可以采用三种方式，具体取决于用户从何处打开树。

1. {"number":1,"type":"Delivery","_parents":[{"number":1,"type":"Order","_parents":[{"number":1,"type":"Quote"}]}]}

2. {"number":1,"type":"Order","_parents":[{"number":1,"type":"Quote"}], "_children":[{"number":1,"type":"Delivery"}]}

3. {"number":1,"type":"Quote","_children":[{"number":1,"type":"Order","_children":[{"number":1,"type":"Delivery"}]}]}

Answer 1

你说你...

need to find the length of the longest chain in that datasource.

这是数据结构中从根到最深叶的长度。有方便的D3方法可以快速找到最深的叶子。

所以，假设我们有一个分层数据，如 this :

{
    "name": "Eve",
    "children": [{
        "name": "Cain"
    }, {
        "name": "Seth",
        "children": [{
            "name": "Enos"
        }, {
            "name": "Noam"
        }]
    }, {
        "name": "Abel"
    }, {
        "name": "Awan",
        "children": [{
            "name": "Enoch"
        }]
    }, {
        "name": "Azura"
    }]
}

当您将其传递给d3.hierarchy()时...

var hierarchy = d3.hierarchy(data);

...它会自动在每个节点中创建一个名为 深度 的属性:

node.depth - zero for the root node, and increasing by one for each descendant generation.

所以，我们只需要一个简单的函数来获取最大的深度值。例如:

var longest = d3.max(hierarchy.descendants().map(function(d) {
    return d.depth
}));

这是一个演示:

var data = {
  "name": "Eve",
  "children": [{
    "name": "Cain"
  }, {
    "name": "Seth",
    "children": [{
      "name": "Enos"
    }, {
      "name": "Noam"
    }]
  }, {
    "name": "Abel"
  }, {
    "name": "Awan",
    "children": [{
      "name": "Enoch"
    }]
  }, {
    "name": "Azura"
  }]
};

var hierarchy = d3.hierarchy(data);
var longest = d3.max(hierarchy.descendants().map(function(d) {
  return d.depth
}));
console.log("The longest chain has " + (longest + 1) + " levels.")

<script src="https://d3js.org/d3.v4.min.js"></script>