# Java application to list all cycles in an undirected and directed graph

**Problem Statement**

Given a graph `G = (V, E)`

, list all cycles within `G`

.

**Algorithm**

1. Compute a cycle basis of graph `G = (V, E)`

* Find a minimal spanning tree `(V, E')`

of `G`

, using Depth-first search (DFS) and its associated set of back edges

* If `e in B`

is a back edge, insert it into the minimal spanning tree’s edges `E'`

to form a set `E'' = E' + {e}`

. The resulting graph `(V, E'')`

has exactly one cycle, which may be constructed by applying a DFS

2. Generate the *incidence vector* of each cycle in the cycle basis

3. Create all possible combinations of the computed incidence vectors. Let the set of all combinations be `C`

4. Generate a cycle from each incidence vector in `C`

The below described algorithm is implemented in CycleUtil.java

**Full code**

https://github.com/lucaslouca/graph-cycles

**References**

* Algorithmic Approaches To Circuit Enumeration and Applications

* Cycle basis