DFS यानि Depth First Search

DFS एक cave explore करने जैसा है एक tunnel को जितना दूर जाए उतना follow करके, फिर पीछे जाकर अगला tunnel try करके।

In this page:

What is DFS
Recursive DFS
Visited Array
DFS Uses
Complexity

Syntax

markup

def dfs(node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited)

What is DFS

Depth-First Search backtrack करने से पहले एक path को जितना दूर जा सके उतना dive करता है अगला unexplored option try करने के लिए, एक maze को हमेशा पहला turn लेकर solve करने जैसा और सिर्फ एक dead end पर पहुंचने पर retreat करते हुए। यह BFS से contrast करता है, जो पहले एक single path commit करने के बजाय level by level फैलता है।

उदाहरण: What is DFS

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj = {{1,2},{0,3},{0,3},{1,2}};
bool visited[4] = {false};
void dfs(int u) {
	visited[u] = true; cout << u << " ";
	for (int v : adj[u]) if (!visited[v]) dfs(v);
}
int main() {
	cout << "DFS order from 0: ";
	dfs(0);
	return 0;
}

import java.util.*;
public class Main {
	static List<List<Integer>> adj = Arrays.asList(Arrays.asList(1,2), Arrays.asList(0,3), Arrays.asList(0,3), Arrays.asList(1,2));
	static boolean[] visited = new boolean[4];
	static void dfs(int u) {
		visited[u] = true; System.out.print(u + " ");
		for (int v : adj.get(u)) if (!visited[v]) dfs(v);
	}
	public static void main(String[] args) {
		System.out.print("DFS order from 0: ");
		dfs(0);
	}
}

adj = [[1,2],[0,3],[0,3],[1,2]]
visited = [False]*4
def dfs(u):
    visited[u] = True
    print(u, end=" ")
    for v in adj[u]:
        if not visited[v]:
            dfs(v)
print("DFS order from 0:", end=" ")
dfs(0)

#include <stdio.h>
int adj[4][2] = {{1,2},{0,3},{0,3},{1,2}};
int visited[4] = {0};
void dfs(int u) {
	visited[u] = 1;
	printf("%d ", u);
	for (int i = 0; i < 2; i++) if (!visited[adj[u][i]]) dfs(adj[u][i]);
}
int main() {
	printf("DFS order from 0: ");
	dfs(0);
	return 0;
}

Recursive DFS

चूंकि DFS naturally एक 'गहरे जाओ, फिर backtrack करो' pattern follow करता है, call stack खुद track कर सकता है कि अगला किस vertex पर वापस जाना है, इसलिए एक recursive function जो हर unvisited neighbor पर खुद को call करता है लगभग कोई extra bookkeeping के बिना DFS implement करता है।

उदाहरण: Recursive DFS

#include <iostream>
using namespace std;
void goDeep(int depth) {
	if (depth == 0) { cout << "Hit dead end, backtracking"; return; }
	cout << "Descend to depth " << depth << " -> ";
	goDeep(depth - 1);
}
int main() {
	goDeep(3);
	return 0;
}

public class Main {
	static void goDeep(int depth) {
		if (depth == 0) { System.out.print("Hit dead end, backtracking"); return; }
		System.out.print("Descend to depth " + depth + " -> ");
		goDeep(depth - 1);
	}
	public static void main(String[] args) {
		goDeep(3);
	}
}

def go_deep(depth):
    if depth == 0:
        print("Hit dead end, backtracking", end="")
        return
    print(f"Descend to depth {depth} -> ", end="")
    go_deep(depth - 1)
go_deep(3)

#include <stdio.h>
void goDeep(int depth) {
	if (depth == 0) { printf("Hit dead end, backtracking"); return; }
	printf("Descend to depth %d -> ", depth);
	goDeep(depth - 1);
}
int main() {
	goDeep(3);
	return 0;
}

Visited Array

Visited vertices track किए बिना, DFS किसी cycle वाले किसी भी graph पर हमेशा के लिए loop करेगा, उन्हीं nodes को endlessly revisit करते हुए। एक vertex के पहली बार enter होते ही मार्क किया गया एक boolean array (या set) recursion को इसे फिर explore करने से रोकता है।

उदाहरण: Visited Array

#include <iostream>
using namespace std;
int adj[3][1] = {{1},{2},{0}};
bool visited[3] = {false};
void dfs(int u, int depth) {
	if (depth > 5) { cout << "would loop forever without visited check"; return; }
	if (visited[u]) { cout << "already visited " << u << ", stop recursing"; return; }
	visited[u] = true;
	dfs(adj[u][0], depth+1);
}
int main() { dfs(0, 0); return 0; }

public class Main {
	static int[][] adj = {{1},{2},{0}};
	static boolean[] visited = new boolean[3];
	static void dfs(int u) {
		if (visited[u]) { System.out.print("already visited " + u + ", stop recursing"); return; }
		visited[u] = true;
		dfs(adj[u][0]);
	}
	public static void main(String[] args) { dfs(0); }
}

adj = [[1],[2],[0]]
visited = [False]*3
def dfs(u):
    if visited[u]:
        print(f"already visited {u}, stop recursing", end="")
        return
    visited[u] = True
    dfs(adj[u][0])
dfs(0)

#include <stdio.h>
int adj[3][1] = {{1},{2},{0}};
int visited[3] = {0};
void dfs(int u) {
	if (visited[u]) { printf("already visited %d, stop recursing", u); return; }
	visited[u] = 1;
	dfs(adj[u][0]);
}
int main() { dfs(0); return 0; }

DFS Uses

DFS connected components ढूंढने, दो vertices के बीच एक path मौजूद है या नहीं जांचने, cycles detect करने, और topological orderings compute करने के लिए standard tool है — कहीं भी जहां आपको किसी starting point से reachability पूरी तरह explore करनी हो।

उदाहरण: DFS Uses

#include <iostream>
using namespace std;
int main() {
	cout << "DFS: connected components, path existence, cycle detection, topological order";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DFS: connected components, path existence, cycle detection, topological order");
	}
}

print("DFS: connected components, path existence, cycle detection, topological order")

#include <stdio.h>
int main() {
	printf("DFS: connected components, path existence, cycle detection, topological order");
	return 0;
}

Complexity

एक adjacency list उपयोग करते समय हर vertex एक बार visited होता है और हर edge एक बार examine होता है, O(V+E) time देते हुए; एक adjacency matrix इसके बजाय O(V²) लेता है क्योंकि sparse graphs के लिए भी हर row scan की जानी चाहिए।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "DFS with adjacency list: O(V+E); with adjacency matrix: O(V^2)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DFS with adjacency list: O(V+E); with adjacency matrix: O(V^2)");
	}
}

print("DFS with adjacency list: O(V+E); with adjacency matrix: O(V^2)")

#include <stdio.h>
int main() {
	printf("DFS with adjacency list: O(V+E); with adjacency matrix: O(V^2)");
	return 0;
}

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson BFS Breadth First Search Next Lesson → Cycle Detection