Cycle Detection Algorithms in Java
There are several algorithms available in Java to detect cycles in a graph. Two of the most commonly used algorithms are the Depth-First Search (DFS) algorithm and the Floyd-Warshall algorithm.
Depth-First Search (DFS) Algorithm
The Depth-First Search (DFS) algorithm is a graph traversal algorithm that can be used to detect cycles in a graph. The basic idea is to start from a vertex and explore as far as possible along each branch before backtracking.
Here's a Java implementation of the DFS algorithm to detect cycles in a directed graph:
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class CycleDetector {
public static boolean hasCycle(Map<Integer, Set<Integer>> graph) {
Set<Integer> visited = new HashSet<>();
Set<Integer> currentPath = new HashSet<>();
for (int vertex : graph.keySet()) {
if (dfs(graph, vertex, visited, currentPath)) {
return true;
}
}
return false;
}
private static boolean dfs(Map<Integer, Set<Integer>> graph, int vertex, Set<Integer> visited, Set<Integer> currentPath) {
visited.add(vertex);
currentPath.add(vertex);
for (int neighbor : graph.get(vertex)) {
if (!visited.contains(neighbor) && dfs(graph, neighbor, visited, currentPath)) {
return true;
} else if (currentPath.contains(neighbor)) {
return true;
}
}
currentPath.remove(vertex);
return false;
}
}
Floyd-Warshall Algorithm
The Floyd-Warshall algorithm is another algorithm that can be used to detect cycles in a graph. It is a dynamic programming algorithm that can find the shortest paths between all pairs of vertices in a weighted graph.
Here's a Java implementation of the Floyd-Warshall algorithm to detect cycles in a weighted graph:
public class CycleDetector {
public static boolean hasCycle(int[][] graph) {
int n = graph.length;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] > graph[i][k] + graph[k][j]) {
return true;
}
}
}
}
return false;
}
}
Both the DFS and Floyd-Warshall algorithms have their own strengths and weaknesses, and the choice of which to use depends on the specific requirements of the problem at hand.
