如何获取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：

test3→test2→test1

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

计算这个的最佳方法是什么？最后，我想要test1的最长链接数。在示例中，它是3：

test3→测试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行。 。

Answer 2

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