javascript - 有向无环层次图实现
问题描述
我需要显示一个看起来有点像这样的无环有向图:
我创建了一个类似于这样的嵌套分层数据结构:
[
{
node: 'abs'
children: [
{
node: 'jhg',
children: [{...}]
{
node: 'AAA',
children: [{...}]
},
{
node: 'fer'
children: [
{
node: 'AAA',
children: [{...}]
{
node: 'xcv',
children: [{...}]
},
{
]
我不确定这是否是实际显示数据的最佳方式,因为具有多个父节点及其子节点的节点会出现多次,但我不知道如何处理它。
我只是想将这些节点渲染到一个假想的网格中。因此我需要解析我的数据结构并设置它们的网格值。问题是我不知道如何用层次逻辑解析数据结构。
我现在正在做的事情显然会导致具有多个父节点的节点出现问题:
for (const root of allRoots) {
currentLevel = 0;
if (root.node === 'VB8') {
getChildrenTree(root);
}
}
function getChildrenTree(node) {
currentLevel++;
node._gridX = currentLevel;
if (node.children.length > 0) {
for(const nextChild of children ) {
getChildrenTree(nextChild);
}
}
这段代码的问题是它只会通过一条路径,然后在没有任何子节点时停止。
我只需要一个贯穿树并设置每个节点层次结构级别的算法。
我希望这不会太混乱。
解决方案
如果要从两个不同的父节点引用同一个节点,则不应多次定义它。我建议列出具有单个“不可见”根节点的平面数组中的所有节点,并通过 id 或数组索引引用子节点:
[
{id: 0, name: "root", children: [1, 2]},
{id: 1, name: "abs", children: [3, 4]},
{id: 2, name: "fer", children: [5, 6]},
{id: 3, name: "jhg", children: [...]},
{id: 4, name: "AAA", children: [...]},
...
]
然后你可以像这样递归地设置它们的树深度:
function setDepth(node, depth) {
if (node._gridX && node._gridX >= depth) {
// node has been visited already through a path of greater or equal length
// so tree depths wouldn't change
return
}
node._gridX = depth
node.children
.map(idx => nodeArray[idx]) // get the actual objects from indices
.forEach(child => setDepth(child, depth+1))
}
setDepth(nodeArray[0], 0) // start at root
...但要小心,因为如果您的节点有任何循环,此算法将陷入循环
推荐阅读
- c - ANSI C 中字符的位操作
- python - 如何在不移动鼠标的情况下在 python 中执行单击?
- html - 当大小文件 html 输出超过 5 MB 时出现问题 rmarkdown
- c - 传递指针以放置在数组中
- amazon-s3 - 如何使用 python 和 boto3 改进获取对象大小?
- unity3d - 试图只查看二维数组的一部分以优化我的代码但不起作用
- machine-learning - 在自然语言处理中是否有减少词汇量的好方法?
- ssl - 允许用户对我的云端应用程序使用自定义域
- datatables - 将值相乘并在数据表中应用样式
- java - 如何在 Jmeter beanshell 脚本中使用 Hashset/set