javascript - 如何获取指向javascript对象属性的链接数

Question

我有这个数据:

const main = 'test1';
const data = [
  {
    from: 'test1',
    to: 'test2'
  },
  {
    from: 'test2',
    to: 'test3'
  },
  {
    from: 'test3',
    to: 'test4'
  },
  {
    from: 'test4',
    to: 'test2'
  },
  {
    from: 'test1',
    to: 'test4'
  }
];

我想获取主节点的链接数(在本例中为 test1)。例如，如果我们查看节点 test3，它需要 2 个链接才能到达 test1:

测试 3 → 测试 2 → 测试 1

与节点 test2 相同，需要 1 个链接才能到达 test1。

最好的计算方法是什么？最后，我想要最长 数量的链接到test1。在示例中是 3:

测试 3 → 测试 2 → 测试 4 → 测试 1

Answer 1

您需要访问每条可能的路径。然而，如果遇到循环并且目标节点可达，则最长距离变为无穷大，因为一个人可能会多次经历该循环。

要访问所有路径，可以使用递归函数。

这是一个:

function find(data, sourceName, targetName) {
    // Create hash data structure keying nodes by their name
    const map = new Map(data.map(({from}) => [from, []]));
    data.forEach(({from,to}) => map.get(from).push(map.get(to)));
    // If links are supposed to be undirected, allowing traversal in both directions
    //   then uncomment this:
    // data.forEach(({from,to}) => map.get(to).push(map.get(from)));
    const target = map.get(targetName);
    // Recursive function
    function recur(node) {
        if (node === target) return 0; // Found target
        if (node.visited) { // Cycle; mark node for detection during backtracking 
            node.onCycle = true;
            return -Infinity;
        }
        node.visited = true;
        let dist = 1 + Math.max(...node.map(recur)); // Maximise path length
        node.visited = false;
        // Leave out next line if longest path should not include cycles
        if (node.onCycle && dist > 0) return Infinity; // Solution path can have cycles
        return dist;
    }
    const dist = recur(map.get(sourceName)); // Start!
    return dist < 0 ? null : dist; // Return null when target cannot be reached
}

const data = [{from: 'test1', to: 'test2'},{from: 'test2', to: 'test3'},{from: 'test3',to: 'test4'},{from: 'test4',to: 'test2'},{from: 'test1',to:'test4'}];
const longestDist = find(data, 'test1', 'test3');
console.log(longestDist);

请注意，此解决方案不会继续通过目标节点进行搜索，然后尝试从那里再次找到它(通过一个循环)。换句话说，它假设一条路径可能只包含目标作为其最后一个节点，而不是多次。

如果您想排除具有循环的路径，则删除返回 Infinity 作为距离的行。

代码假定链接是定向的。如果链接被理解为双向(又名未定向)，这意味着如果指定了一个方向，则相反的方向也可以，而无需明确将其作为镜像链接，然后取消注释上面代码中的第二行 forEach。