Depth-First Search (DFS) Algorithm Code Implementations
Complete Depth-First Search (DFS) Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Depth-First Search (DFS) Algorithm Guide ยท Launch Interactive Visualizer
C++ Implementation
// Depth-First Search Implementation in C++
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
class DepthFirstSearch {
public:
static std::vector<int> depthFirstSearch(const std::unordered_map<int, std::vector<int>>& graph, int start) {
std::unordered_set<int> visited;
std::vector<int> result;
dfs(graph, start, visited, result);
return result;
}
private:
static void dfs(const std::unordered_map<int, std::vector<int>>& graph, int node,
std::unordered_set<int>& visited, std::vector<int>& result) {
visited.insert(node);
result.push_back(node);
auto it = graph.find(node);
if (it != graph.end()) {
for (int neighbor : it->second) {
if (visited.find(neighbor) == visited.end()) {
dfs(graph, neighbor, visited, result);
}
}
}
}
public:
// DFS with iterative approach using stack
static std::vector<int> depthFirstSearchIterative(const std::unordered_map<int, std::vector<int>>& graph, int start) {
std::unordered_set<int> visited;
std::stack<int> stack;
std::vector<int> result;
visited.insert(start);
stack.push(start);
while (!stack.empty()) {
int current = stack.top();
stack.pop();
result.push_back(current);
auto it = graph.find(current);
if (it != graph.end()) {
const std::vector<int>& neighbors = it->second;
for (int i = neighbors.size() - 1; i >= 0; i--) {
int neighbor = neighbors[i];
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
stack.push(neighbor);
}
}
}
}
return result;
}
// DFS for finding cycles
static bool depthFirstSearchCycleDetection(const std::unordered_map<int, std::vector<int>>& graph) {
std::unordered_set<int> visited;
std::unordered_set<int> recStack;
bool hasCycle = false;
for (const auto& [node, neighbors] : graph) {
if (visited.find(node) == visited.end()) {
dfsCycle(graph, node, visited, recStack, hasCycle);
}
}
return hasCycle;
}
private:
static void dfsCycle(const std::unordered_map<int, std::vector<int>>& graph, int node,
std::unordered_set<int>& visited, std::unordered_set<int>& recStack, bool& hasCycle) {
visited.insert(node);
recStack.insert(node);
auto it = graph.find(node);
if (it != graph.end()) {
for (int neighbor : it->second) {
if (visited.find(neighbor) == visited.end()) {
dfsCycle(graph, neighbor, visited, recStack, hasCycle);
} else if (recStack.find(neighbor) != recStack.end()) {
hasCycle = true;
}
}
}
recStack.erase(node);
}
public:
// DFS for topological sorting
static std::vector<int> depthFirstSearchTopologicalSort(const std::unordered_map<int, std::vector<int>>& graph) {
std::unordered_set<int> visited;
std::unordered_set<int> recStack;
std::vector<int> result;
bool hasCycle = false;
for (const auto& [node, neighbors] : graph) {
if (visited.find(node) == visited.end()) {
dfsTopological(graph, node, visited, recStack, result, hasCycle);
}
}
return hasCycle ? std::vector<int>{} : result;
}
private:
static void dfsTopological(const std::unordered_map<int, std::vector<int>>& graph, int node,
std::unordered_set<int>& visited, std::unordered_set<int>& recStack,
std::vector<int>& result, bool& hasCycle) {
if (hasCycle) return;
visited.insert(node);
recStack.insert(node);
auto it = graph.find(node);
if (it != graph.end()) {
for (int neighbor : it->second) {
if (visited.find(neighbor) == visited.end()) {
dfsTopological(graph, neighbor, visited, recStack, result, hasCycle);
} else if (recStack.find(neighbor) != recStack.end()) {
hasCycle = true;
}
}
}
recStack.erase(node);
result.insert(result.begin(), node);
}
public:
// DFS for connected components
static std::vector<std::vector<int>> depthFirstSearchConnectedComponents(const std::unordered_map<int, std::vector<int>>& graph) {
std::unordered_set<int> visited;
std::vector<std::vector<int>> components;
for (const auto& [node, neighbors] : graph) {
if (visited.find(node) == visited.end()) {
std::vector<int> component;
dfsComponent(graph, node, visited, component);
components.push_back(component);
}
}
return components;
}
private:
static void dfsComponent(const std::unordered_map<int, std::vector<int>>& graph, int node,
std::unordered_set<int>& visited, std::vector<int>& component) {
visited.insert(node);
component.push_back(node);
auto it = graph.find(node);
if (it != graph.end()) {
for (int neighbor : it->second) {
if (visited.find(neighbor) == visited.end()) {
dfsComponent(graph, neighbor, visited, component);
}
}
}
}
};JAVA Implementation
// Depth-First Search Implementation in Java
import java.util.*;
public class DepthFirstSearch {
public static List<Integer> depthFirstSearch(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
List<Integer> result = new ArrayList<>();
dfs(graph, start, visited, result);
return result;
}
private static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, List<Integer> result) {
visited.add(node);
result.add(node);
List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
for (int neighbor : neighbors) {
if (!visited.contains(neighbor)) {
dfs(graph, neighbor, visited, result);
}
}
}
// DFS with iterative approach using stack
public static List<Integer> depthFirstSearchIterative(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Stack<Integer> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
visited.add(start);
stack.push(start);
while (!stack.isEmpty()) {
int current = stack.pop();
result.add(current);
List<Integer> neighbors = graph.getOrDefault(current, new ArrayList<>());
for (int i = neighbors.size() - 1; i >= 0; i--) {
int neighbor = neighbors.get(i);
if (!visited.contains(neighbor)) {
visited.add(neighbor);
stack.push(neighbor);
}
}
}
return result;
}
// DFS for finding cycles
public static boolean depthFirstSearchCycleDetection(Map<Integer, List<Integer>> graph) {
Set<Integer> visited = new HashSet<>();
Set<Integer> recStack = new HashSet<>();
boolean[] hasCycle = {false};
for (int node : graph.keySet()) {
if (!visited.contains(node)) {
dfsCycle(graph, node, visited, recStack, hasCycle);
}
}
return hasCycle[0];
}
private static void dfsCycle(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited,
Set<Integer> recStack, boolean[] hasCycle) {
visited.add(node);
recStack.add(node);
List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
for (int neighbor : neighbors) {
if (!visited.contains(neighbor)) {
dfsCycle(graph, neighbor, visited, recStack, hasCycle);
} else if (recStack.contains(neighbor)) {
hasCycle[0] = true;
}
}
recStack.remove(node);
}
// DFS for topological sorting
public static List<Integer> depthFirstSearchTopologicalSort(Map<Integer, List<Integer>> graph) {
Set<Integer> visited = new HashSet<>();
Set<Integer> recStack = new HashSet<>();
List<Integer> result = new ArrayList<>();
boolean[] hasCycle = {false};
for (int node : graph.keySet()) {
if (!visited.contains(node)) {
dfsTopological(graph, node, visited, recStack, result, hasCycle);
}
}
return hasCycle[0] ? null : result;
}
private static void dfsTopological(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited,
Set<Integer> recStack, List<Integer> result, boolean[] hasCycle) {
if (hasCycle[0]) return;
visited.add(node);
recStack.add(node);
List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
for (int neighbor : neighbors) {
if (!visited.contains(neighbor)) {
dfsTopological(graph, neighbor, visited, recStack, result, hasCycle);
} else if (recStack.contains(neighbor)) {
hasCycle[0] = true;
}
}
recStack.remove(node);
result.add(0, node);
}
// DFS for connected components
public static List<List<Integer>> depthFirstSearchConnectedComponents(Map<Integer, List<Integer>> graph) {
Set<Integer> visited = new HashSet<>();
List<List<Integer>> components = new ArrayList<>();
for (int node : graph.keySet()) {
if (!visited.contains(node)) {
List<Integer> component = new ArrayList<>();
dfsComponent(graph, node, visited, component);
components.add(component);
}
}
return components;
}
private static void dfsComponent(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, List<Integer> component) {
visited.add(node);
component.add(node);
List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
for (int neighbor : neighbors) {
if (!visited.contains(neighbor)) {
dfsComponent(graph, neighbor, visited, component);
}
}
}
}JAVASCRIPT Implementation
// Depth-First Search Implementation in JavaScript
function depthFirstSearch(graph, start) {
const visited = new Set();
const result = [];
function dfs(node) {
visited.add(node);
result.push(node);
const neighbors = graph[node] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
dfs(neighbor);
}
}
}
dfs(start);
return result;
}
// DFS with iterative approach using stack
function depthFirstSearchIterative(graph, start) {
const visited = new Set();
const stack = [start];
const result = [];
visited.add(start);
while (stack.length > 0) {
const current = stack.pop();
result.push(current);
const neighbors = graph[current] || [];
for (let i = neighbors.length - 1; i >= 0; i--) {
const neighbor = neighbors[i];
if (!visited.has(neighbor)) {
visited.add(neighbor);
stack.push(neighbor);
}
}
}
return result;
}
// DFS for finding cycles
function depthFirstSearchCycleDetection(graph) {
const visited = new Set();
const recStack = new Set();
const hasCycle = { value: false };
function dfs(node) {
visited.add(node);
recStack.add(node);
const neighbors = graph[node] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
dfs(neighbor);
} else if (recStack.has(neighbor)) {
hasCycle.value = true;
}
}
recStack.delete(node);
}
for (const node in graph) {
if (!visited.has(node)) {
dfs(node);
}
}
return hasCycle.value;
}
// DFS for topological sorting
function depthFirstSearchTopologicalSort(graph) {
const visited = new Set();
const recStack = new Set();
const result = [];
const hasCycle = { value: false };
function dfs(node) {
if (hasCycle.value) return;
visited.add(node);
recStack.add(node);
const neighbors = graph[node] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
dfs(neighbor);
} else if (recStack.has(neighbor)) {
hasCycle.value = true;
}
}
recStack.delete(node);
result.unshift(node);
}
for (const node in graph) {
if (!visited.has(node)) {
dfs(node);
}
}
return hasCycle.value ? null : result;
}
// DFS for connected components
function depthFirstSearchConnectedComponents(graph) {
const visited = new Set();
const components = [];
function dfs(node, component) {
visited.add(node);
component.push(node);
const neighbors = graph[node] || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
dfs(neighbor, component);
}
}
}
for (const node in graph) {
if (!visited.has(node)) {
const component = [];
dfs(node, component);
components.push(component);
}
}
return components;
}PYTHON Implementation
# Depth-First Search Implementation in Python
def depth_first_search(graph, start):
visited = set()
result = []
def dfs(node):
visited.add(node)
result.append(node)
neighbors = graph.get(node, [])
for neighbor in neighbors:
if neighbor not in visited:
dfs(neighbor)
dfs(start)
return result
# DFS with iterative approach using stack
def depth_first_search_iterative(graph, start):
visited = set()
stack = [start]
result = []
visited.add(start)
while stack:
current = stack.pop()
result.append(current)
neighbors = graph.get(current, [])
for neighbor in reversed(neighbors):
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
return result
# DFS for finding cycles
def depth_first_search_cycle_detection(graph):
visited = set()
rec_stack = set()
has_cycle = [False]
def dfs(node):
visited.add(node)
rec_stack.add(node)
neighbors = graph.get(node, [])
for neighbor in neighbors:
if neighbor not in visited:
dfs(neighbor)
elif neighbor in rec_stack:
has_cycle[0] = True
rec_stack.remove(node)
for node in graph:
if node not in visited:
dfs(node)
return has_cycle[0]
# DFS for topological sorting
def depth_first_search_topological_sort(graph):
visited = set()
rec_stack = set()
result = []
has_cycle = [False]
def dfs(node):
if has_cycle[0]:
return
visited.add(node)
rec_stack.add(node)
neighbors = graph.get(node, [])
for neighbor in neighbors:
if neighbor not in visited:
dfs(neighbor)
elif neighbor in rec_stack:
has_cycle[0] = True
rec_stack.remove(node)
result.insert(0, node)
for node in graph:
if node not in visited:
dfs(node)
return None if has_cycle[0] else result
# DFS for connected components
def depth_first_search_connected_components(graph):
visited = set()
components = []
def dfs(node, component):
visited.add(node)
component.append(node)
neighbors = graph.get(node, [])
for neighbor in neighbors:
if neighbor not in visited:
dfs(neighbor, component)
for node in graph:
if node not in visited:
component = []
dfs(node, component)
components.append(component)
return components