[FIXED] How should I find cycle in the directed graph and list out the nodes which are forming the cycle?

Issue

I have the array of objects in javascript i am trying to draw the directed graph how should i find whether it contains cycle or not if contains what are the elements forming the cycle Graph is not strongly connected and nodes can be isolated like "f"

 array = {};
//operations   parents
    array[a] = [b,c]
    array[b] = [d,c]
    array[e] = [a,b]
    array[d] = [e]
    array[f] = []

I want to find the cycle between the operations like here we have cycle from e-d-b-e? How should i find the cycle? I am using javascript.

Solution

Here is a BFS solution that will find one cycle (if there are any), which will be (one of) the shortest one(s).

function getCycle(graph) {
    // Copy the graph, converting all node references to String
    graph = Object.assign(...Object.keys(graph).map( node =>
                ({ [node]: graph[node].map(String) }) 
    ));

    let queue = Object.keys(graph).map( node => [node] );
    while (queue.length) {
        const batch = [];
        for (const path of queue) {
            const parents = graph[path[0]] || [];
            for (const node of parents) {
                if (node === path[path.length-1]) return [node, ...path];
                batch.push([node, ...path]);
            }
        }
        queue = batch;
    }
}

// First example
var graph = {
    a: ['b', 'c'],
    b: ['d', 'c'],
    e: ['a', 'b'],
    d: ['e']
};
var result = getCycle(graph);
console.log(result);

// Second example (numeric node references)
var graph = {
    0: [4],
    1: [4,0],
    2: [0,1],
    3: [1],
    4: [3]
};
var result = getCycle(graph);
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

NB: If you define your graph with number references, a type conversion is needed since object properties are always of type string. We could use == instead of ===, but then the output will still be a mix of string and numbers; I think it is nicer to first convert every node reference to string.

Answered By - trincot

Answer Checked By - David Marino (PHPFixing Volunteer)