**Get started with Spring 5 and Spring Boot 2, through the ***Learn Spring* course:

*Learn Spring*course:

**>> CHECK OUT THE COURSE**

Last modified: June 14, 2019

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

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

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.

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

- If
- 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.

Let's consider the below cyclic directed graph:

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

```
@Test
public 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.

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.