[java] 사이클 찾기 알고리즘
이번 포스트에서는 자바에서 사이클을 찾는 알고리즘에 대해 알아보겠습니다. 사이클을 찾는 알고리즘은 그래프 구조에서 특정한 노드로부터 시작하여 다시 해당 노드로 돌아오는 경로를 찾는 알고리즘입니다.
깊이 우선 탐색(Depth First Search, DFS)
깊이 우선 탐색은 그래프에서 각 노드를 탐색할 때 깊이를 우선하여 탐색하는 알고리즘입니다. 이 알고리즘을 활용하여 사이클을 찾을 수 있습니다. 다음은 자바에서 DFS로 사이클을 찾는 예시 코드입니다.
public class CycleDetection {
private static boolean hasCycle = false;
public static boolean detectCycle(Graph graph) {
int n = graph.getNumVertices();
boolean[] visited = new boolean[n];
boolean[] recStack = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfs(graph, visited, recStack, i)) {
hasCycle = true;
break;
}
}
}
return hasCycle;
}
private static boolean dfs(Graph graph, boolean[] visited, boolean[] recStack, int vertex) {
visited[vertex] = true;
recStack[vertex] = true;
List<Integer> neighbors = graph.getNeighbors(vertex);
for (int neighbor : neighbors) {
if (!visited[neighbor]) {
if (dfs(graph, visited, recStack, neighbor)) {
return true;
}
} else if (recStack[neighbor]) {
return true;
}
}
recStack[vertex] = false;
return false;
}
}
위의 코드는 Graph 객체를 입력으로 받아서 DFS 알고리즘을 이용하여 사이클을 찾는 기능을 제공합니다. Graph 객체는 그래프의 정보를 담고 있으며, getNumVertices() 메서드로 정점의 개수를 확인하고, getNeighbors(int vertex) 메서드로 해당 정점과 연결된 모든 정점의 리스트를 가져옵니다.
사용 예시
public class Main {
public static void main(String[] args) {
// 그래프 생성
Graph graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 0);
boolean hasCycle = CycleDetection.detectCycle(graph);
if (hasCycle) {
System.out.println("그래프에 사이클이 존재합니다.");
} else {
System.out.println("그래프에 사이클이 존재하지 않습니다.");
}
}
}
위의 예시 코드는 0부터 4까지의 정점들로 이루어진 그래프에 각 정점들을 순환하는 사이클이 존재하는지를 확인하는 예시입니다. CycleDetection.detectCycle(graph) 메서드를 호출하여 사이클 존재 여부를 확인할 수 있습니다.
마치며
이번 포스트에서는 자바에서 사이클을 찾는 알고리즘을 소개했습니다. 깊이 우선 탐색 알고리즘을 이용하여 그래프에서 사이클을 찾을 수 있으며, 위의 예시 코드를 참고하여 구현해보세요.