我想检查一个图形在 JavaScript 中是否是循环的。我有两个数组,第一个数组中的每个项目都与第二个数组的(相同索引)项目有关系。
举个例子:first = [4, 2, 3, 1]
second = [2, 3, 1, 4]
所以 4=>2、2=>3、3=>1 和 1=4 之间存在关系。当您查看图表时,您可以看到它是循环的。
我写了这段代码,但它返回 false
虽然它应该返回 true
对于以下输入;first = [2, 1, 3, 4]
second = [3, 2, 1, 3]
我怎样才能做到这一点?我需要使用图算法吗?
function ifGraphCyclic(first, second) {
let nodes = new Map();
let unique = [];
for (let i = 0; i < first.length; i++) {
nodes.set(first[i], second[i]);
}
for (let value of nodes.values()) {
unique.push(nodes.get(value));
}
if (first.length === new Set(unique).size) {
return true;
}
return false;
}
console.log(ifGraphCyclic([4, 2, 3, 1], [2, 3, 1, 4])) // return true
console.log(ifGraphCyclic([2, 1, 3, 4], [3, 2, 1, 3])) // *return false but should return true*
console.log(ifGraphCyclic([1, 2, 2, 4, 4, 5, 6], [2, 3, 4, 5, 6, 6, 3])) // return false
console.log(ifGraphCyclic([1, 2, 2, 4, 5, 6, 6], [2, 3, 4, 5, 6, 3, 4])) // *return false but should return true*
最佳答案
您可以使用数组收集对象中节点的所有关系并检查是否看到节点。
function ifGraphCyclic(first, second) {
const nodes = first.reduce((r, v, i) => ((r[v] = r[v] || []).push(second[i]), r), {});
for (let n of first) {
const queue = [[n, []]];
while (queue.length) {
const [node, seen] = queue.shift();
if (!(node in nodes)) continue;
if (seen.includes(node)) {
console.log(...seen, n);
return true;
}
seen.push(node);
queue.push(...nodes[node].map(a => [a, [...seen]]));
}
}
return false;
}
console.log(ifGraphCyclic([4, 2, 3, 1], [2, 3, 1, 4])); // 4 2 3 1 4
console.log(ifGraphCyclic([2, 1, 3, 4], [3, 2, 1, 3])); // 2 3 1 2
console.log(ifGraphCyclic([3, 4, 2, 1], [1, 3, 4, 2])); // 3 1 2 4 3
console.log(ifGraphCyclic([3, 4, 2, 1], [1, 3, 4, 5])); // 2 4 3 1 5
console.log(ifGraphCyclic([1, 2, 2, 4, 4, 5, 6], [2, 3, 4, 5, 6, 6, 3]));
.as-console-wrapper { max-height: 100% !important; top: 0; }
关于javascript - 如何在 JavaScript 中检查图形是否循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66049922/