Cycle Detection
Cycle in Graph
A cycle exists when you can start at some vertex, follow edges, and eventually return to that same vertex without repeating an edge — like a circular hallway that eventually leads back to where you started.
Example: Cycle in Graph
#include <iostream>
using namespace std;
int main() {
int path[] = {0, 1, 2, 0};
cout << "Path 0->1->2->0 returns to start without repeating an edge: cycle found";
return 0;
}public class Main {
public static void main(String[] args) {
int[] path = {0, 1, 2, 0};
System.out.println("Path 0->1->2->0 returns to start without repeating an edge: cycle found");
}
}path = [0, 1, 2, 0]
print("Path 0->1->2->0 returns to start without repeating an edge: cycle found")#include <stdio.h>
int main() {
int path[] = {0, 1, 2, 0};
printf("Path 0->1->2->0 returns to start without repeating an edge: cycle found");
return 0;
}Login to try C/C++/Java code in the editor
Visited Vertices
Marking each vertex as visited during traversal lets you spot a cycle the moment you reach a vertex that's already been visited earlier in the current exploration, rather than for the first time.
Example: Visited Vertices
#include <iostream>
using namespace std;
int adj[3][1] = {{1},{2},{0}};
bool visited[3] = {false};
bool dfs(int u) {
if (visited[u]) return true;
visited[u] = true;
return dfs(adj[u][0]);
}
int main() {
cout << (dfs(0) ? "Cycle found: revisited an already-visited vertex" : "No cycle");
return 0;
}public class Main {
static int[][] adj = {{1},{2},{0}};
static boolean[] visited = new boolean[3];
static boolean dfs(int u) {
if (visited[u]) return true;
visited[u] = true;
return dfs(adj[u][0]);
}
public static void main(String[] args) {
System.out.println(dfs(0) ? "Cycle found: revisited an already-visited vertex" : "No cycle");
}
}adj = [[1],[2],[0]]
visited = [False]*3
def dfs(u):
if visited[u]:
return True
visited[u] = True
return dfs(adj[u][0])
print("Cycle found: revisited an already-visited vertex" if dfs(0) else "No cycle")#include <stdio.h>
int adj[3][1] = {{1},{2},{0}};
int visited[3] = {0};
int dfs(int u) {
if (visited[u]) return 1;
visited[u] = 1;
return dfs(adj[u][0]);
}
int main() {
printf(dfs(0) ? "Cycle found: revisited an already-visited vertex" : "No cycle");
return 0;
}Login to try C/C++/Java code in the editor
Undirected Graph
In an undirected graph every edge you arrive on immediately makes the vertex you came from look 'already visited,' so DFS must explicitly ignore the edge back to the immediate parent — otherwise every single edge would be flagged as a false cycle.
Example: Undirected Graph
#include <iostream>
using namespace std;
int adj[3][2] = {{1,2},{0,2},{0,1}};
int adjCount[3] = {2,2,2};
bool visited[3] = {false};
bool dfs(int u, int parent) {
visited[u] = true;
for (int i = 0; i < adjCount[u]; i++) {
int v = adj[u][i];
if (v == parent) continue;
if (visited[v]) return true;
if (dfs(v, u)) return true;
}
return false;
}
int main() {
cout << (dfs(0, -1) ? "Cycle found (ignoring the edge back to parent)" : "No cycle");
return 0;
}public class Main {
static int[][] adj = {{1,2},{0,2},{0,1}};
static boolean[] visited = new boolean[3];
static boolean dfs(int u, int parent) {
visited[u] = true;
for (int v : adj[u]) {
if (v == parent) continue;
if (visited[v]) return true;
if (dfs(v, u)) return true;
}
return false;
}
public static void main(String[] args) {
System.out.println(dfs(0, -1) ? "Cycle found (ignoring the edge back to parent)" : "No cycle");
}
}adj = [[1,2],[0,2],[0,1]]
visited = [False]*3
def dfs(u, parent):
visited[u] = True
for v in adj[u]:
if v == parent:
continue
if visited[v] or dfs(v, u):
return True
return False
print("Cycle found (ignoring the edge back to parent)" if dfs(0, -1) else "No cycle")#include <stdio.h>
int adj[3][2] = {{1,2},{0,2},{0,1}};
int visited[3] = {0};
int dfs(int u, int parent) {
visited[u] = 1;
for (int i = 0; i < 2; i++) {
int v = adj[u][i];
if (v == parent) continue;
if (visited[v] || dfs(v, u)) return 1;
}
return 0;
}
int main() {
printf(dfs(0, -1) ? "Cycle found (ignoring the edge back to parent)" : "No cycle");
return 0;
}Login to try C/C++/Java code in the editor
Directed Graph
Directed graphs need a second marker beyond visited: a vertex must be flagged as part of the current recursion path (in-progress), since revisiting a vertex that finished earlier in a different branch is not a cycle, but revisiting one still on the current path is.
Example: Directed Graph
#include <iostream>
using namespace std;
int adj[3][1] = {{1},{2},{0}};
bool visited[3] = {false}, inStack[3] = {false};
bool dfs(int u) {
visited[u] = true; inStack[u] = true;
int v = adj[u][0];
if (inStack[v]) return true;
if (!visited[v] && dfs(v)) return true;
inStack[u] = false;
return false;
}
int main() {
cout << (dfs(0) ? "Cycle: vertex still in current recursion path" : "No cycle");
return 0;
}public class Main {
static int[][] adj = {{1},{2},{0}};
static boolean[] visited = new boolean[3], inStack = new boolean[3];
static boolean dfs(int u) {
visited[u] = true; inStack[u] = true;
int v = adj[u][0];
if (inStack[v]) return true;
if (!visited[v] && dfs(v)) return true;
inStack[u] = false;
return false;
}
public static void main(String[] args) {
System.out.println(dfs(0) ? "Cycle: vertex still in current recursion path" : "No cycle");
}
}adj = [[1],[2],[0]]
visited = [False]*3
in_stack = [False]*3
def dfs(u):
visited[u] = True
in_stack[u] = True
v = adj[u][0]
if in_stack[v]:
return True
if not visited[v] and dfs(v):
return True
in_stack[u] = False
return False
print("Cycle: vertex still in current recursion path" if dfs(0) else "No cycle")#include <stdio.h>
int adj[3][1] = {{1},{2},{0}};
int visited[3] = {0}, inStack[3] = {0};
int dfs(int u) {
visited[u] = 1; inStack[u] = 1;
int v = adj[u][0];
if (inStack[v]) return 1;
if (!visited[v] && dfs(v)) return 1;
inStack[u] = 0;
return 0;
}
int main() {
printf(dfs(0) ? "Cycle: vertex still in current recursion path" : "No cycle");
return 0;
}Login to try C/C++/Java code in the editor
Why Detect Cycles
Detecting cycles matters for practical reasons: a circular dependency between software packages would cause an infinite build loop, and a cycle in a course-prerequisite graph would make it impossible to ever satisfy every requirement.
Example: Why Detect Cycles
#include <iostream>
using namespace std;
int main() {
cout << "Package A depends on B depends on A: circular dependency, build loops forever";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Package A depends on B depends on A: circular dependency, build loops forever");
}
}print("Package A depends on B depends on A: circular dependency, build loops forever")#include <stdio.h>
int main() {
printf("Package A depends on B depends on A: circular dependency, build loops forever");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: