← Back to DSA Course | Chapter 13: Graphs | Lesson 5 of 10

Cycle Detection कैसे करें

Cycle detection यह जांचने जैसा है कि आप one-way streets follow करके वहीं वापस आ सकते हैं जहां से शुरू हुए थे।

In this page:

  1. Cycle in Graph
  2. Visited Vertices
  3. Undirected Graph
  4. Directed Graph
  5. Why Detect Cycles
Syntax
markup 
def has_cycle(node, parent, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle(neighbor, node, visited):
                return True
        elif neighbor != parent:
            return True
    return False

Cycle in Graph

एक cycle मौजूद है जब आप किसी vertex से शुरू कर सकते हैं, edges follow कर सकते हैं, और आखिरकार उसी vertex पर बिना किसी edge दोहराए वापस आ सकते हैं — एक circular hallway जैसा जो आखिरकार वापस वहां ले जाता है जहां से आप शुरू हुए।

उदाहरण: 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;
}

Visited Vertices

Traversal के दौरान हर vertex को visited मार्क करना आपको एक cycle पहचानने देता है जैसे ही आप उस vertex तक पहुंचें जो पहले current exploration में visited हो चुका है, पहली बार के बजाय।

उदाहरण: 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;
}

Undirected Graph

एक undirected graph में आप जिस भी edge पर आते हैं वह तुरंत उस vertex को 'already visited' जैसा दिखाता है जहां से आप आए, इसलिए DFS को immediate parent की वापसी वाले edge को explicitly नज़रअंदाज़ करना चाहिए — नहीं तो हर single edge को एक false cycle के रूप में flag किया जाएगा।

उदाहरण: 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;
}

Directed Graph

Directed graphs को visited से आगे एक दूसरा marker चाहिए: एक vertex को current recursion path के हिस्से (in-progress) के रूप में flag किया जाना चाहिए, क्योंकि एक अलग branch में पहले खत्म हुए vertex को फिर से visit करना एक cycle नहीं है, लेकिन अब भी current path पर एक को revisit करना है।

उदाहरण: 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;
}

Why Detect Cycles

Cycles detect करना practical कारणों से मायने रखता है: software packages के बीच एक circular dependency एक infinite build loop का कारण बनेगी, और एक course-prerequisite graph में एक cycle हर requirement को कभी satisfy करना असंभव बना देगी।

उदाहरण: 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;
}
Related Topics

Floyd का Cycle Detection Algorithm · DFS यानि Depth First Search · Topological Sort क्या है · BFS यानि Breadth First Search

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. एक directed graph पर undirected algorithm उपयोग करना, इसलिए अलग paths से दो बार पहुंचा एक vertex एक cycle के रूप में report होता है।
  2. एक undirected graph में, parent को एक visited neighbor की तरह treat करना, जो हर edge के लिए एक cycle report करता है।
  3. एक directed graph में, call return होने पर recursion stack से एक vertex unmark करना भूल जाना।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson DFS Depth First Search Next Lesson → Topological Sort

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.