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

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_c0f6f

到 S_007f5 的路径

A_fbb03 -> W_c0f6f -> S_007f5 -> A_fbb03

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

函数returnfalse

有什么改进此解决方案的建议吗？

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

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

Find path between nodes in flat array

javascript

arrays

tree