在数组中查找对象的Javascript算法

Question

我有一个对象数组，其中包含有关项目的数据。每个项目都有一个ID和两个数组，其中包含项目的ID，这将在项目之前和之后发生。像这样：

let projects = [];
projects[0] = {
id: "ID_123",
before: [],
after: ["ID_523"],
}
projects[1] = {
id: "ID_523",
before: ["ID_123"],
after: ["ID_523","ID_827"],
}

我想找到所有相互依赖的项目，并将它们添加到同一个子组中。因此，我循环遍历数组，并从以前没有项目发生的项目开始。然后我不断地添加第一个项目，将其添加到同一个子组中，并一直这样做，直到以后没有更多的项目发生。我的算法：

let subgroup = 0;
// loop through project array
for (let i=0; i<projects.length; i++) {
let next = projects[i]; // next contains the next project in the row
// find projects that have no projects happening before
if ((!next.hasOwnProperty('subgroup')) && (next.before.length == 0)) {
// do this as long as the next project has projects happening after
while (next.after.length > 0) {
// find the array-key of the first project happening afterwards
let key;
for (let n=0; n<projects.length; n++) {
if (projects[n].id == next.after[0]) {
key = n;
break;
}
}
// set the subgroup of the project with the key from above
projects[key].subgroup = subgroup;
// set the next project
next = projects[key];
}
subgroup++;
}
}

不幸的是，该算法没有按预期工作，有些项目根本无法分配子组。我花了好几天时间查找错误，但找不到。

希望有人能告诉我我做错了什么。提前感谢！

Answer 1

您缺少连接，因为您的代码只查看after[0]，而不查看可能出现在after属性中的任何其他ID。更重要的是，您还应该通过before检查依赖关系，因为您可能会从不同的前辈访问一个项目，然后这些项目都应该属于同一个子组。

您还可以避免迭代您需要查找的每个ID的数据：相反，创建一个Map，该Map将根据每个项目的ID对其进行键控。

然后，为了确保处理after和before属性中的所有条目，执行广度优先搜索：将所有依赖项目添加到队列中，忽略已访问的项目(我将使用Set(：

let projects = [{
id: "ID_123",
before: [],
after: ["ID_523"],
}, {
id: "ID_523",
before: ["ID_123"],
after: ["ID_523","ID_827"],
}, {
id: "ID_827",
before: ["ID_523"],
after: [],
}, {
id: "ID_999",
before: [],
after: [],
}];

let subgroup = 0;
let map = new Map(projects.map(p => [p.id, p]));
for (let project of projects) {
if (project.before.length === 0 && !("subgroup" in project)) {
let todo = new Set([project]);
for (let project of todo) {
project.subgroup = subgroup;
for (let next of project.after) todo.add(map.get(next));
for (let prev of project.before) todo.add(map.get(prev));
}
subgroup++;
}
}
console.log(projects);