## 1. Overview

In this quick tutorial, we'll learn how we can** detect a cycle in a given directed graph.**

## 2. Graph Representation

For this tutorial, we'll stick with the adjacency list graph representation.

Firstly, let's start by defining a *Vertex* in Java:

```
public class Vertex {
private String label;
private boolean beingVisited;
private boolean visited;
private List<Vertex> adjacencyList;
public Vertex(String label) {
this.label = label;
this.adjacencyList = new ArrayList<>();
}
public void addNeighbor(Vertex adjacent) {
this.adjacencyList.add(adjacent);
}
//getters and setters
}
```

**Here, the ***adjacencyList* of a vertex* v* holds a list of all vertices adjacent to *v*. The *addNeighbor()* method adds a neighboring vertex to the adjacency list of *v*.

We've also defined two *boolean* parameters,** ***beingVisited *and* visited,* which represent whether the node is currently being visited or has already been visited.

A graph can be thought of as a group of vertices or nodes connected through the edges.

So, let's now quickly represent a *Graph* in Java:

```
public class Graph {
private List<Vertex> vertices;
public Graph() {
this.vertices = new ArrayList<>();
}
public void addVertex(Vertex vertex) {
this.vertices.add(vertex);
}
public void addEdge(Vertex from, Vertex to) {
from.addNeighbor(to);
}
// ...
}
```

We'll use the *addVertex()* and* addEdge()* methods to add new vertices and edges in our graph.

## 3. Cycle Detection

To detect a cycle in a directed graph,** we'll use a variation of ***DFS* traversal:

- Pick up an unvisited vertex
*v* and mark its state as *beingVisited*
- For each neighboring vertex
*u *of *v, *check:
- If
*u* is already in the *beingVisited* state, it clearly means** there exists a backward edge and so a cycle has been detected**
- If
*u* is yet in an unvisited state, we'll recursively visit* u *in a depth-first manner

- Update the vertex
*v*‘s *beingVisited* flag to *false* and its *visited* flag to *true*

Note that** all the vertices of our graph are initially in an unvisited state as both their ***beingVisited* and *visited* flags are initialized with *false*.

Let's now look at our Java solution:

```
public boolean hasCycle(Vertex sourceVertex) {
sourceVertex.setBeingVisited(true);
for (Vertex neighbor : sourceVertex.getAdjacencyList()) {
if (neighbor.isBeingVisited()) {
// backward edge exists
return true;
} else if (!neighbor.isVisited() && hasCycle(neighbor)) {
return true;
}
}
sourceVertex.setBeingVisited(false);
sourceVertex.setVisited(true);
return false;
}
```

We can use any vertex in a graph to be the source or the starting vertex.

**For a disconnected graph, we'll have to add an additional wrapper method:**

```
public boolean hasCycle() {
for (Vertex vertex : vertices) {
if (!vertex.isVisited() && hasCycle(vertex)) {
return true;
}
}
return false;
}
```

This is to ensure that we visit every component of a disconnected graph for detecting a cycle.

## 4. Implementation Testing

Let's consider the below cyclic directed graph:

We can quickly write a JUnit to verify our *hasCycle()* method for this graph:

```
@Test
void givenGraph_whenCycleExists_thenReturnTrue() {
Vertex vertexA = new Vertex("A");
Vertex vertexB = new Vertex("B");
Vertex vertexC = new Vertex("C")
Vertex vertexD = new Vertex("D");
Graph graph = new Graph();
graph.addVertex(vertexA);
graph.addVertex(vertexB);
graph.addVertex(vertexC);
graph.addVertex(vertexD);
graph.addEdge(vertexA, vertexB);
graph.addEdge(vertexB, vertexC);
graph.addEdge(vertexC, vertexA);
graph.addEdge(vertexD, vertexC);
assertTrue(graph.hasCycle());
}
```

Here, our *hasCycle()* method returned *true* denoting that our graph is cyclic.

## 5. Conclusion

In this tutorial, we learned how to check if a cycle exists in a given directed graph in Java.

As usual, the code implementation with examples is available over on Github.

res – REST with Spring (eBook) (everywhere)