我有一个元素列表,每个元素都有一个ID和一个父ID。我想做的是检测这个"层次结构"中何时存在循环,并显示哪个 ID 启动循环。
list = [
{
id: '1',
parent: '2'
},
{
id: '2',
parent: '3'
},
{
id: '3',
parent: '4'
},
{
//This id is causing the loop
id: '4',
parent: '1'
}
]
我已经尝试过构建树,该树在没有循环时有效,但不适用于循环:
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;
};
我也无法检测到何时有循环。
我想返回导致循环的元素的 ID,以允许我修复它背后的数据。
您可以应用白-灰-黑颜色来检测在访问其后代时(重新(访问的节点(我已将您的图表简化为父子对列表(:
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/
您可以收集对象中的所有节点和子节点,并通过获取访问过的节点数组来过滤所有节点。
无限数组包含导致循环引用的所有节点。
function isCircular(id, visited = []) {
return visited.includes(id)
|| Object.keys(links[id]).some(k => isCircular(k, visited.concat(id)));
}
var list = [{ id: '1', parent: '2' }, { id: '2', parent: '3' }, { id: '3', parent: '4' }, { id: '4', parent: '1' }],
links = {},
infinite = [];
list.forEach(({ id, parent }) => {
links[parent] = links[parent] || {};
links[parent][id] = true;
});
infinite = list.filter(({ id }) => isCircular(id));
console.log(links);
console.log(infinite);
.as-console-wrapper { max-height: 100% !important; top: 0; }