arrays - How to check if a graph is cyclic in JavaScript

Question

I would like to check if a graph is cyclic in JavaScript. I have two arrays and each item in first array has a relation with (same index) item of second array.

Let's give an example: first = [4, 2, 3, 1] second = [2, 3, 1, 4]

So there are relations between 4=>2, 2=>3, 3=>1 and 1=4. When you look at the graph, you can see that it is cyclic.

I wrote this code but it is returning false although it should return true for the following input;

first = [2, 1, 3, 4] second = [3, 2, 1, 3]

How can I achieve this? Do I need to use graph algorithm?

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*

question from:https://stackoverflow.com/questions/66049922/how-to-check-if-a-graph-is-cyclic-in-javascript

Answer 1

You could collect all relations of the nodes in an object with arrays and check if a node is seen.

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