AntInLoop

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