Understand Depth First Search Problem

Problem Name: Depth First Search

Problem Description:

Depth-First Search (DFS) Algorithm

What is DFS?

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It can be implemented using recursion or an explicit stack.

DFS Algorithm:

Start from the root (or any arbitrary node).
Mark the node as visited.
Explore each adjacent unvisited node recursively.
Backtrack when no more unvisited nodes are found.

Example:

Let's consider a simple graph: A / \ B C / \ \ D E F

Adjacency List Representation:

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B"],
  F: ["C"]
};

Output:

A B D E C F

Complexity Analysis

Time Complexity:

O(V + E) where V is the number of vertices and E is the number of edges.

Space Complexity:

O(V) for storing visited nodes in recursion.

Use Cases of DFS:

Pathfinding algorithms (e.g., Maze solving)
Detecting cycles in graphs
Topological sorting
Connected components in a graph

Category:
Graphs
Searching
Binary Trees

Programming Language:
Java

Reference Link:

https://drawtocode.vercel.app/problems/depth-first-search

Online IDE

Scroll down for output

Java

Output:

Loading component...

Tracking code (View only. In case you want to track the code, click this button):

Main Function:

INPUT : graph = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F"], D: ["B"], E: ["B"], F: ["C"] }

OUTPUT: A B D E C F

public static void main(String[] args) {

Map<Character, List<Character>> graph = new HashMap<>();

graph.put('A', Arrays.asList('B', 'C'));

graph.put('B', Arrays.asList('A', 'D', 'E'));

graph.put('C', Arrays.asList('A', 'F'));

graph.put('D', Arrays.asList('B'));

graph.put('E', Arrays.asList('B'));

graph.put('F', Arrays.asList('C'));

Set<Character> visited = new HashSet<>();

dfs(graph, 'A', visited);

}//function end

Helper Function:

static void dfs(Map<Character, List<Character>> graph, char node, Set<Character> visited) {

if (visited.contains(node)) {

return;

}

System.out.print(node + " ");

visited.add(node);

for (char neighbor : graph.getOrDefault(node, new ArrayList<>())) {

dfs(graph, neighbor, visited);

} //Loop End

}//function End

Utility Functions and Global variables:

Utility Function is not required.