如何获取 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'
  }
];

我想获取到主节点的link个数（本例为test1）。例如，如果我们查看节点 test3，需要 2 links 才能到达 test1:

test3 → test2 → test1

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

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

test3 → test2 → test4 → test1

Answer 1

您的问题可以用图论术语重新定义："test1"、"test2"、...是顶点，数据数组包含边（对 "from-to"）- 所以我们有图 - 在图中找到最长路径是 NP 难问题 - wiki。所以你需要检查所有可能的路径以找到最长的

Answer 2

您需要访问每条可能的路径。但是如果遇到一个循环并且目标节点是可达的，那么最长的距离就变成无穷大，因为一个人可能会经历这个循环任意多次。

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

这是一个：

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);

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

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

代码假定 link 是 定向的 。如果 link 被理解为双向（a.k.a 未定向 ），这意味着如果指定了一个方向，则相反的方向也是可能的没有明确地将其包含为镜像 link，然后取消注释上面代码中的第二行 forEach。

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

How to get number of links to javascript object property

javascript

arrays

json

graph-algorithm

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

How to get number of links to javascript object property

javascript

arrays

json

graph-algorithm

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