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.

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.

• javascript
• algorithm
• data-structures
• graph

• if you run a dfs on this graph and if you reach at the same node from where you started at some point, congrats you have found a cycle in any graph :p – zenwraight Commented Aug 16, 2017 at 14:44
• What are the a, b, c, ... variables in your script, and is that all you have? – trincot Commented Aug 16, 2017 at 14:48
• a,b,c are not variables they are the values these are a javascript object as (key,Values) – Ayush Rawat Commented Aug 16, 2017 at 14:50
• If they are not variables, then that is not valid JavaScript. Valid literal values are numbers, strings (they must be quoted), booleans, null or undefined. a is none of those. – trincot Commented Aug 16, 2017 at 14:56
• @trincot that's why I have assumed some values for a,b,c,d,e to show how the algorithm would basically work .... – zenwraight Commented Aug 16, 2017 at 15:15

4 Answers 4

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.

Depth-First Search. If DFS finds an edge that points to an already discovered ancestor of the current node, the graph contains a cycle.

After referring to the ments on @zenwraigts solution I infer that this is a problem of Strongly Connected Components. You can find a good tutorial here, you can find javascript implementations here and here.

How is this a problem of SCC ?

all vertices which form a strongly connected ponent for a cycle, the problem reduces to finding all SCC's and print them

So as I mented, you need to basically traverse through the whole graph and keep a visited array to keep track of nodes that you have visited till now and if you reach any already visited node, then there exists a cycle in the provided directed graph.

To make your work easier here is a running code, you can use it as reference to build your algorithm on it.

Improved my answer little bit, iterating through all nodes, so that it covers some unreachable paths as well. Thank you all :)

array = {};

/*
Assuming 
a = 0
b=  1
c = 2
d = 3
e = 4
*/

// Here I am forming an adjacency list of directed nodes based on the diagram
array[0] = [4];
array[1] = [4,0];
array[2] = [0,1];
array[4] = [3];
array[3] = [1];
visited = {};
visited[0] = 0;
visited[1] = 0;
visited[2] = 0;
visited[3] = 0;
visited[4] = 0;

list_for_cycle_nodes = [];

for(var node = 0; node<5; node++) {
   if (dfs(node)) {
    for (var index = 0; index < list_for_cycle_nodes.length; index++) {
      console.log(list_for_cycle_nodes[index]+" ");
    }
    console.log('There is a cycle');
  } else {
    console.log('Yipee, there is no cycle');
  } 
}

function dfs(s) {
  if(visited[s] == 1) {
    return true;
  }
  list_for_cycle_nodes.push(s);
  visited[s] = 1;
  var flag = false;
  if(array[s].length <= 0) {
    return false;
  }
  for(var index = 0; index<array[s].length; index++) {
    flag = flag | dfs(array[s][index]);
    if(flag) {
      return true;
    }
  }
  return flag;
}

Hope this helps!