✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-104

Depth-First Search (DFS)

Depth-First Search is a graph traversal algorithm that explores one branch as deeply as possible before returning to explore other branches. It uses recursion or an explicit stack and is useful for connectivity, cycle detection, and graph analysis.

Explanation

Overview

Depth-First Search (DFS) is a traversal algorithm that visits a vertex and recursively or iteratively explores an unvisited neighbor before backtracking.

Key concepts

name: Core idea; description: The central focus of depth-first search (dfs) is the capability described here: Depth-First Search is a graph traversal algorithm that explores one branch as deeply as possible before returning to explore other branches. It uses recursion or an explicit stack and is useful for connectivity, cycle detection, and graph analysis.; name: Problem context; description: Depth-First Search (DFS) is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using depth-first search (dfs), check its assumptions, input requirements, expected output, and resource constraints.

Time complexity

adjacencyList: O(V + E); adjacencyMatrix: O(V²)

Space complexity

O(V) for visited information and the recursion or explicit stack in the worst case, excluding graph storage.

Applications

Cycle detection; Connected-component identification; Topological sorting; Finding strongly connected components; Maze and state-space exploration; Path existence checking

Advantages

Uses a simple recursive structure.; Supports many advanced graph algorithms.; Can explore deep structures efficiently.; Works on directed and undirected graphs.

Limitations

Does not guarantee shortest paths.; Recursive implementations may exceed the call-stack limit on deep graphs.; Traversal order depends on neighbor ordering.; A disconnected graph requires additional starting vertices to visit every component.

Example or application

A worked example has not yet been added.

Definition

Depth-First Search (DFS) is a traversal algorithm that visits a vertex and recursively or iteratively explores an unvisited neighbor before backtracking.

Core Principle

Explore deeply before backtracking.

Data Structures

  • Stack

  • Recursion call stack

  • Visited set or boolean array

Algorithm Steps

  • Choose a starting vertex.

  • Mark the starting vertex as visited.

  • Select an unvisited neighboring vertex.

  • Continue exploring from that neighbor.

  • When no unvisited neighbor remains, backtrack.

  • Continue until all vertices reachable from the starting vertex have been explored.

Recursive Pseudocode

DFS(u): mark u visited; for each neighbor v of u: if v is not visited: DFS(v).

Iterative Pseudocode

Push the starting vertex onto a stack. While the stack is not empty, pop a vertex; if it is unvisited, mark it visited and push its unvisited neighbors.

Example Graph

A

  • B

  • C

B

  • D

  • E

C

  • F

D

No items supplied.

E

No items supplied.

F

No items supplied.

Possible Traversal

Start Vertex

A

Order

  • A

  • B

  • D

  • E

  • C

  • F

Note

The exact order depends on the order in which neighbors are processed.

Backtracking

Backtracking occurs when DFS reaches a vertex with no remaining unvisited neighbors and returns to an earlier vertex to continue exploration.

Time Complexity

Adjacency List

O(V + E)

Adjacency Matrix

O(V²)

Space Complexity

O(V) for visited information and the recursion or explicit stack in the worst case, excluding graph storage.

Applications

  • Cycle detection

  • Connected-component identification

  • Topological sorting

  • Finding strongly connected components

  • Maze and state-space exploration

  • Path existence checking

  • Articulation-point and bridge algorithms

Advantages

  • Uses a simple recursive structure.

  • Supports many advanced graph algorithms.

  • Can explore deep structures efficiently.

  • Works on directed and undirected graphs.

Limitations

  • Does not guarantee shortest paths.

  • Recursive implementations may exceed the call-stack limit on deep graphs.

  • Traversal order depends on neighbor ordering.

  • A disconnected graph requires additional starting vertices to visit every component.

Important Considerations

  • Always track visited vertices when traversing graphs that may contain cycles.

  • For undirected cycle detection, distinguish the parent edge from a genuine back edge.

  • For directed cycle detection, track recursion-stack or node colors.

  • An iterative implementation can avoid recursion-depth limitations.

Comparison With BFS

BFS

Uses a queue and explores level by level.

DFS

Uses a stack or recursion and explores deeply before backtracking.

Shortest Path

BFS finds minimum-edge paths in unweighted graphs; DFS does not guarantee this.

Common Complexity

Both run in O(V + E) time with adjacency lists.

Related Concepts

  • Stacks

  • Breadth-First Search

  • Cycle Detection

  • Topological Sorting

  • Strongly Connected Components

Key Concepts

NameDescription

Core idea

The central focus of depth-first search (dfs) is the capability described here: Depth-First Search is a graph traversal algorithm that explores one branch as deeply as possible before returning to explore other branches. It uses recursion or an explicit stack and is useful for connectivity, cycle detection, and graph analysis.

Problem context

Depth-First Search (DFS) is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using depth-first search (dfs), check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of depth-first search (dfs)?

Depth-First Search is a graph traversal algorithm that explores one branch as deeply as possible before returning to explore other branches. It uses recursion or an explicit stack and is useful for connectivity, cycle detection, and graph analysis.

What should be checked before applying depth-first search (dfs)?

For depth-first search (dfs), verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of depth-first search (dfs) be validated?

Trace a representative depth-first search (dfs) case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of depth-first search (dfs).

  • Identify the assumptions, inputs, and conditions relevant to depth-first search (dfs).

  • Evaluate an application of depth-first search (dfs) for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures