查找平面数组中节点之间的路径

Question

我有一个平面连接数组，表示树中节点的连接。

const connections = [
{
id: "first",
source: "root",
target: "A_fbb03",
},
{
source: "A_fbb03",
target: "W_c0f6f",
id: "A_fbb03_W_c0f6f",
},
{
source: "A_fbb03",
target: "W_4c2dd",
id: "A_fbb03_W_4c2dd",
},
{
id: "A_fbb03_W_1f0ac",
source: "A_fbb03",
target: "W_1f0ac",
},
{
id: "W_c0f6f_S_007f5",
source: "W_c0f6f",
target: "S_007f5",
},
];

在节点之间添加新连接时，我想检查此连接是否创建了循环，这意味着目标节点具有指向源节点的路径。

我想出了一个函数：

function isLoopConnection = (newConnection, connections) => {
const theSource = newConnection.source
let theTarget = newConnection.target
let isLoop = false

for (let i = 0; i < connections.length; i++) {
const nextConnection = connections.filter(item => item.source === theTarget)
if (nextConnection.length) {
for (const nc of nextConnection) {
if (nc.target === theSource) {
isLoop = true
break
} else {
theTarget = nc.target
}
}
}
}
return isLoop
}

显然，这在某些情况下效果不佳，感觉太复杂了。 例如：当我添加一个新连接时，假设在S_007f5之间创建一个循环A_fbb03因为A_fbb03有一条通过W_c0f6fS_007f5的途径

A_fbb03 -> W_c0f6f -> S_007f5 -> A_fbb03

{
id: "S_007f5_A_fbb03",
source: "S_007f5",
target: "A_fbb03",
}

函数返回false

任何建议如何改进此解决方案？

Answer 1

您可以采用Set并存储看到的节点标识符。

此方法生成一个包含所有节点的所有子节点的对象。为了获得结果，所有项目都用于检查循环引用。

const
hasLoop = array => {
const
children = array.reduce((r, { source, target }) => ((r[source] ??= []).push(target), r), {}),
check = (node, seen = new Set) => {
if (seen.has(node)) return true;
seen.add(node);
return (children[node] || []).some(node => check(node, seen));
};
return array.some(({ source }) => check(source));
},
connections = [{ source: "root", target: "A_fbb03" }, { source: "A_fbb03", target: "W_c0f6f" }, { source: "A_fbb03", target: "W_4c2dd" }, { source: "A_fbb03", target: "W_1f0ac" }, { source: "W_c0f6f", target: "S_007f5" }, { source: "S_007f5", target: "A_fbb03" }];

console.log(hasLoop(connections.slice(0, -1))); // false
console.log(hasLoop(connections));              //  true