Detecting Graph Cycles With Depth-First Search
Tags: computerscience, algorithms, datastructures, csharp
Published: 2020-02-11 01:41:31

## Resources:

1. [Video on detecting cycles in directed graphs](https://www.youtube.com/watch?v=rKQaZuoUR4M)
1. [Video on detecting cycles in undirected graphs](https://www.youtube.com/watch?v=n_t0a_8H8VY)
1. [MIT video on detecting cycles in graphs](https://youtu.be/AfSk24UTFS8?t=1838)
1. [Helpful implementation for detecting cycles in adjacency matrix](https://leetcode.com/problems/course-schedule/discuss/250882/c-graph-cycle-detection-summary-dfstopological-sortunion-find)
1. [_Deadlock Detection_ in the book: Elements of Programming Interviews](https://www.amazon.com/Elements-Programming-Interviews-Java-Insiders/dp/1517671272/)

To get the most out of this article, it is helpful if you already know what a graph is, and ideally what depth-first search is. [A previous post of mine](https://dev.to/jjb/part-9-learning-graphs-4859) covers the basics of graphs and graph traversals.

Some takeaways:

* A graph cycle is when there is a "loop" or circular reference. This can be a series of edges that connect back to an origin vertex. 
* If a graph has a cycle it is a **cyclic** graph.
* To determine if a graph has a cycle, we can traverse the graph and look for a **back edge**.
   * A back edge is one that connects a vertex to an already visited ancestor.
   * Example:

![Cycle in graph](https://dev-to-uploads.s3.amazonaws.com/i/cl9xn2umoib6rckwz1en.jpg)

* To detect a cycle in a directed graph (i.e to find a back edge), you can use depth-first search (with some introduction of local state to tell you if a back edge occurs):
      * We will maintain 3 buckets of vertices: white, grey, & black buckets. (We can also colour vertices instead).
   * The white bucket will contain all of the _unvisited_ vertices. At the start of our traversal, this means every vertex is in the white bucket.
   * Before visiting a vertex, we will move it from the white bucket into the grey bucket.
   * After fully visiting a vertex, it will get moved from the grey bucket into the black bucket.
   * We can skip over vertices already in the black bucket, if we happen to try and visit them again.
   * When visiting the children/descendants of a vertex, if we come to a descendant vertex that is _already_ in the grey bucket - that means we have found a back edge/cycle.
   * This means the current vertex has a back edge to it's ancestor - as we only arrived at the current vertex via it's ancestor. So we have just determined that there is more than one path between the two (a cycle).
* To detect a cycle in an undirected graph, it is very similar to the approach for a directed graph. However, there are some key differences:
   * We no longer colour vertices/maintain buckets.
   * We have to make sure to account for the fact that edges are bidirectional - so an edge to an ancestor is allowed, if that ancestor is the parent vertex.
   * We only keep track of visited vertices (similar to the grey bucket). 
   * When exploring/visiting all descendants of a vertex, if we come across a vertex that has already been visited then we have detected a cycle.
* Time complexity is `O(v + e)` for an adjacency list. Space complexity is `O(v)`. For an adjacency matrix, the time & space complexity would be `O(v^2)`.

Although using depth-first search is common for cycle detection, you can also detect cycles using __topological sort__ too. I have yet to cover topological sorting of graphs - but will be doing so in a later post.

Below are implementations of cycle detection via depth-first search in both undirected & directed graphs. I have implemented each for an adjacency list (`Graph`) & an adjacency matrix (`Graph2`):

{% gist https://gist.github.com/jbolton209/f8a422d3c2270e5e1ca7de413a4ab99d %}

As always, if you found any errors in this post please let me know!