Cycles Algorithm
In graph theory, a cycle in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. A directed cycle in a directed graph is a non-empty directed trail in which the only repeated are the first and last vertices.
A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree.
In his 1736 paper on the Seven Bridges of Königsberg, widely considered to be the birth of graph theory, Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once, it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex.
package DataStructures.Graphs;
import java.util.Scanner;
import java.util.ArrayList;
class Cycle {
private int nodes, edges;
private int[][] adjacencyMatrix;
private boolean[] visited;
ArrayList<ArrayList<Integer>> cycles = new ArrayList<ArrayList<Integer>>();
public Cycle() {
Scanner in = new Scanner(System.in);
System.out.print("Enter the no. of nodes: ");
nodes = in.nextInt();
System.out.print("Enter the no. of Edges: ");
edges = in.nextInt();
adjacencyMatrix = new int[nodes][nodes];
visited = new boolean[nodes];
for (int i = 0; i < nodes; i++) {
visited[i] = false;
}
System.out.println("Enter the details of each edges <Start Node> <End Node>");
for (int i = 0; i < edges; i++) {
int start, end;
start = in.nextInt();
end = in.nextInt();
adjacencyMatrix[start][end] = 1;
}
in.close();
}
public void start() {
for (int i = 0; i < nodes; i++) {
ArrayList<Integer> temp = new ArrayList<>();
dfs(i, i, temp);
for (int j = 0; j < nodes; j++) {
adjacencyMatrix[i][j] = 0;
adjacencyMatrix[j][i] = 0;
}
}
}
private void dfs(Integer start, Integer curr, ArrayList<Integer> temp) {
temp.add(curr);
visited[curr] = true;
for (int i = 0; i < nodes; i++) {
if (adjacencyMatrix[curr][i] == 1) {
if (i == start) {
cycles.add(new ArrayList<Integer>(temp));
} else {
if (!visited[i]) {
dfs(start, i, temp);
}
}
}
}
if (temp.size() > 0) {
temp.remove(temp.size() - 1);
}
visited[curr] = false;
}
public void printAll() {
for (int i = 0; i < cycles.size(); i++) {
for (int j = 0; j < cycles.get(i).size(); j++) {
System.out.print(cycles.get(i).get(j) + " -> ");
}
System.out.println(cycles.get(i).get(0));
System.out.println();
}
}
}
public class Cycles {
public static void main(String[] args) {
Cycle c = new Cycle();
c.start();
c.printAll();
}
}
