我有这些数据:
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
您需要访问每条可能的路径。但是,如果遇到一个循环并且目标节点是可达的,则最长距离变为无穷大,因为可以经历该循环任何次数。
要访问所有路径,可以使用递归函数。
这是一个:
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
行。 。
您的问题可以用图论理论术语重新定义:“test1”,“test2”,......是顶点,数据数组包含边(对“从 - 到”) - 所以我们有图 - 找到图中最长的路径是NP难题 - wiki。因此,您需要检查所有可能的路径以找到最长的路径