如何在 JavaScript 中检查图是否是循环图

Question

我想检查 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*

Answer 1

您可以使用数组收集对象中节点的所有关系，并检查是否看到节点。

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