如何在JavaScript元素的层次结构中检测循环 [英] How to detect a loop in a hierarchy of javascript elements
问题描述
我有一个元素列表,每个元素都有一个ID和一个父ID.我想做的是检测此层次结构"中是否存在循环,并显示哪个ID开始循环.
I have a list of elements, each has an ID and a parent ID. What I want to do is detect when there is a loop in this 'hierarchy', and show which ID starts the loop.
list = [
{
id: '1',
parent: '2'
},
{
id: '2',
parent: '3'
},
{
id: '3',
parent: '4'
},
{
//This id is causing the loop
id: '4',
parent: '1'
}
]
我已经尝试过构建树,该树在没有循环的情况下可以使用,但是在没有循环的情况下可以使用:
I have tried this to build the tree, which works when there's no loop, but does not work with a loop:
function treeify(list, idAttr, parentAttr, childrenAttr) {
if (!idAttr) idAttr = 'id';
if (!parentAttr) parentAttr = 'parent';
if (!childrenAttr) childrenAttr = 'children';
var treeList = [];
var lookup = {};
list.forEach(function(obj) {
lookup[obj[idAttr]] = obj;
obj[childrenAttr] = [];
});
list.forEach(function(obj) {
if (obj[parentAttr] != null) {
lookup[obj[parentAttr]][childrenAttr].push(obj);
} else {
treeList.push(obj);
}
});
return treeList;
};
我也无法检测到何时出现循环.
I also cannot detect when there is a loop.
我想返回导致循环的元素的ID,以便我修复其背后的数据.
I'd like to return the ID of the element that caused the loop to allow me to fix the data behind it.
推荐答案
您可以应用白色-灰色-黑色着色来检测在访问其后代时被(重新)访问的节点(我已将您的图形简化为亲子对):
You can apply white-grey-black coloring to detect nodes that are (re)visited while visiting their descendants (I've simplified your graph to a list of parent-child pairs):
graph = [
[2, 1],
[3, 2],
[1300023, 3],
[1, 1300023],
];
colors = {}
function visit(vertex) {
if (colors[vertex] === 'black') {
// black = ok
return;
}
if (colors[vertex] === 'grey') {
// grey = visited while its children are being visited
// cycle!
console.log('cycle', colors);
return;
}
// mark as being visited
colors[vertex] = 'grey';
// visit children
graph.forEach(edge => {
if (edge[0] === vertex)
visit(edge[1]);
});
// mark as visited and ok
colors[vertex] = 'black'
}
visit(1)
此方法的一个很好的例子: https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/
A nice illustration of this approach: https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/
这篇关于如何在JavaScript元素的层次结构中检测循环的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!