Identifying cycle in directed graph

This post is a note to self on how to identify cycle in directed graph with Breadth first search and Depth first search.

Cycle

In graph theory, a cycle is a path in a graph that starts and ends at the same vertex. In other words, a cycle is a closed path in a graph that does not pass through any vertex more than once, except for the starting and ending vertex which are the same.

In the graph above there is cycle. A->B->C->A

DFS

The first thing which comes to my mind is to simply reuse the undirected graph logic which I discussed in the previous post. So as an exercise try that algorithm on the following graph and you will notice that it will not work.

To fix the problem we will introduce three new states:

1. When a node is not yet processed we will color it white this is same as unvisited node.
2. When a node is being processed (that is not all of its neighbours are fully explored). we will color such node with gray.
3. When a node has been processed and all of its neighbours are also processed we will color it black.

Now when exploring the neighbours of gray if we encounter another gray node that would be that their is a cycle. so our algorithm become:

const [WHITE, GRAY, BLACK] = [0, 1, 2];

const isCycle = (node, graph, colors) => {
  colors[node] = GRAY // mark the node being processed gray
  for(const neighbour of graph[node]) {
    if (color[neighbour] === GRAY) return true; // return true as their is cycle
    if (color[neighbour] === WHITE && isCycle(neighbour, graph, colors)) return true
  }
  colors[node] = BLACK // we have processed the node
  return false;
}

BFS

For the Breadth First Approach we will use Topological Sorting. This is called Kahns Algorithm

Topological sorting is a technique used to order the nodes in a directed acyclic graph in such a way that for every directed edge from node A to node B, A comes before B in the ordering. In other words, it is a linear ordering of the nodes in a graph such that if there is a directed edge from node A to node B, then A appears before B in the ordering.

Lets see an example suppose you have the following graph

These are the possible topological sorting:

1. (0, 2, 3, 4, 1, 5)
2. (4, 0, 2, 3, 1, 5)

These values are obtained by apply the following algorithm on the graph:

function topologicalSort(graph) {
  const inDegree = new Map();
  const queue = [];
  const sorted = [];

  for (let node of graph.getNodes()) {
    inDegree.set(node, 0);
  }

  for (let node of graph.getNodes()) {
    for (let neighbor of graph.getNeighbors(node)) {
      inDegree.set(neighbor, inDegree.get(neighbor) + 1);
    }
  }

  for (let [node, degree] of inDegree) {
    if (degree === 0) {
      queue.push(node);
    }
  }

  while (queue.length) {
    const node = queue.shift();
    sorted.push(node);

    for (let neighbor of graph.getNeighbors(node)) {
      inDegree.set(neighbor, inDegree.get(neighbor) - 1);

      if (inDegree.get(neighbor) === 0) {
        queue.push(neighbor);
      }
    }
  }

  if (sorted.length !== graph.getNodes().length) {
    throw new Error("Graph has a cycle!");
  }

  return sorted;
}

Topological sorting is only applicable for directed and graph without a cycle. If the directed graph has cycle its topological sorting is not possible see the example below

Note that topological sort can also be performed via DFS.